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.
// 4ms, 95%
/*
1. count the number of each unique char
2. recursively call count(), each level calculates a different length of possible sequence
In the first level, take one from each unique char, represents a size 1 sequence
In the next level, take one from each unique char, combining with previous char forms a size 2 sequences
*/
class Solution {
int count(vector<int>& buf) {
int sum = 0;
for (int i = 0; i < 26; i++) {
if (buf[i] > 0) {
sum++;
buf[i]--;
sum += count(buf);
buf[i]++;
}
}
return sum;
}
public:
int numTilePossibilities(string tiles) {
vector<int> buf(26, 0);
for (const auto& c : tiles)
buf[c - 'A']++;
return count(buf);
}
};