##### Welcome to Subscribe On Youtube

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

• 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);
}
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>();
nextPermutation(array);
while (!Arrays.equals(array, sorted)) {
String str = new String(array);
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:

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