You have n 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 using the letters printed on those tiles.
Example 1:
Input: tiles = "AAB" Output: 8 Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".
Example 2:
Input: tiles = "AAABBC" Output: 188
Example 3:
Input: tiles = "V"
Output: 1
Depth First Search Solution, which is more performant with time complexity of O(N!) and space complexity of O(N).
class Solution {
public:
int numTilePossibilities(string tiles) {
unordered_map<char, int> count;
for (char c : tiles) {
count[c]++;
}
return dfs(count);
}
private:
int dfs(unordered_map<char, int>& count) {
int sum = 0;
for (auto& [tile, cnt] : count) {
if (cnt == 0) continue;
sum++;
count[tile]--;
sum += dfs(count);
count[tile]++;
}
return sum;
}
};
Backtracking Solution:
class Solution {
private:
set<string> seq;
void backtrack(const string& tiles, string& current, vector<bool>& used){
if( !current.empty() )
seq.insert( current );
for( int i =0; i<tiles.length();i++){
if(used[i]) continue;
used[i]=true;
current.push_back(tiles[i]);
backtrack(tiles, current, used);
current.pop_back();
used[i]=false;
}
}
public:
int numTilePossibilities(string tiles) {
vector<bool> used(tiles.length(), false);
string current = "";
backtrack(tiles, current, used);
return seq.size();
}
};Optimized Backtracking solution:
class Solution {
public:
void backtrack(unordered_map<char,int>&mapi,int &count){
for(auto&entry:mapi){
if(entry.second>0){
entry.second--;
count++;
backtrack(mapi,count);
entry.second++;
}
}
}
int numTilePossibilities(string tiles) {
unordered_map<char,int>mapi;
for(int i=0;i<tiles.size();i++){
mapi[tiles[i]]++;
}
int count=0;
backtrack(mapi,count);
return count;
}
};