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);
        }
    }
    
  • // 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;
        }
    };
    
  • # 1079. Letter Tile Possibilities
    # https://leetcode.com/problems/letter-tile-possibilities/
    
    class Solution:
        def numTilePossibilities(self, tiles: str) -> int:
            res = set()
    
            def dfs(curr, word):
                if curr not in res:
                    if curr:
                        res.add(curr)
    
                    for i in range(len(word)):
                        dfs(curr + word[i], word[:i] + word[i + 1:])
            
            dfs('', tiles)
            
            return len(res)
    
    

All Problems

All Solutions