Formatted question description: https://leetcode.ca/all/1079.html

1079. Letter Tile Possibilities (Medium)

You have a set of tiles, where each tile has one letter tiles[i] printed on it.  Return the number of possible non-empty sequences of letters you can make.

 

Example 1:

Input: "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

Example 2:

Input: "AAABBC"
Output: 188

 

Note:

1. 1 <= tiles.length <= 7
2. tiles consists of uppercase English letters.

Solution 1.

// OJ: https://leetcode.com/problems/letter-tile-possibilities/

// Time: O(2^N)
// Space: O(N)
class Solution {
private:
    int ans = 0, cnts[26] = {};
    long long count(int n) {
        long long val = 1;
        for (int i = 1; i <= n; ++i) val *= i;
        return val;
    }
    void updateAns() {
        long long total = 0, div = 1;
        for (int i = 0; i < 26; ++i) {
            total += cnts[i];
            div *= count(cnts[i]);
        }
        ans += count(total) / div;
    }
    void compute(string &A, int begin) {
        if (begin == A.size()) {
            updateAns();
            return;
        }
        cnts[A[begin] - 'A']++;
        compute(A, begin + 1);
        cnts[A[begin] - 'A']--;
        do { ++begin; } while (begin < A.size() && A[begin] == A[begin - 1]);
        compute(A, begin);
    }
public:
    int numTilePossibilities(string tiles) {
        sort(tiles.begin(), tiles.end());
        compute(tiles, 0);
        return ans - 1;
    }
};

Java

class Solution {
    public int numTilePossibilities(String tiles) {
        Set<String> allTiles = new HashSet<String>();
        int length = tiles.length();
        int maxCombinations = (int) Math.pow(2, length);
        for (int i = 1; i < maxCombinations; i++) {
            Set<String> permutations = permutations(tiles, i);
            allTiles.addAll(permutations);
        }
        return allTiles.size();
    }

    public Set<String> permutations(String tiles, int index) {
        int length = tiles.length();
        int[] binary = new int[length];
        int remain = index;
        for (int i = length - 1; i >= 0; i--) {
            int remainder = remain % 2;
            binary[i] = remainder;
            remain /= 2;
            if (remain == 0)
                break;
        }
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < length; i++) {
            if (binary[i] == 1)
                sb.append(tiles.charAt(i));
        }
        char[] array = sb.toString().toCharArray();
        char[] sorted = sb.toString().toCharArray();
        Arrays.sort(array);
        Arrays.sort(sorted);
        Set<String> set = new HashSet<String>();
        set.add(new String(array));
        nextPermutation(array);
        while (!Arrays.equals(array, sorted)) {
            String str = new String(array);
            set.add(str);
            nextPermutation(array);
        }
        return set;
    }

    public void nextPermutation(char[] array) {
        int length = array.length;
        int index = -1;
        char curC = 0;
        for (int i = length - 1; i > 0; i--) {
            int difference = array[i] - array[i - 1];
            if (difference > 0) {
                index = i - 1;
                curC = array[index];
                break;
            }
        }
        if (index < 0) {
            Arrays.sort(array);
            return;
        }
        int nextIndex = -1;
        char nextC = 'a';
        for (int i = index + 1; i < length; i++) {
            if (array[i] > curC && array[i] < nextC) {
                nextIndex = i;
                nextC = array[i];
            }
        }
        array[index] = nextC;
        array[nextIndex] = curC;
        Arrays.sort(array, index + 1, length);
    }
}

All Problems

All Solutions