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 <= tiles.length <= 7
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;
    }
};

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);
    }
}

############

class Solution {
    public int numTilePossibilities(String tiles) {
        int[] cnt = new int[26];
        for (char c : tiles.toCharArray()) {
            ++cnt[c - 'A'];
        }
        return dfs(cnt);
    }

    private int dfs(int[] cnt) {
        int res = 0;
        for (int i = 0; i < cnt.length; ++i) {
            if (cnt[i] > 0) {
                ++res;
                --cnt[i];
                res += dfs(cnt);
                ++cnt[i];
            }
        }
        return res;
    }
}

// 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;
    }
};

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        def dfs():
            ans = 0
            for i in range(26):
                if cnt[i]:
                    ans += 1
                    cnt[i] -= 1
                    ans += dfs()
                    cnt[i] += 1
            return ans

        cnt = [0] * 26
        for t in tiles:
            cnt[ord(t) - ord('A')] += 1
        return dfs()

############

# 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)

func numTilePossibilities(tiles string) int {
	cnt := make([]int, 26)
	for _, c := range tiles {
		cnt[c-'A']++
	}
	var dfs func() int
	dfs = func() int {
		res := 0
		for i := 0; i < 26; i++ {
			if cnt[i] > 0 {
				res++
				cnt[i]--
				res += dfs()
				cnt[i]++
			}
		}
		return res
	}
	return dfs()
}

1079 - Letter Tile Possibilities

1079. Letter Tile Possibilities (Medium)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

1079. Letter Tile Possibilities (Medium)

Solution 1.

All Problems

All Solutions