Letter Tile Possibilities Solutions in C++

/// Source : https://leetcode.com/problems/letter-tile-possibilities/
/// Author : liuyubobobo
/// Time   : 2019-06-08

#include <iostream>
#include <algorithm>
#include <unordered_set>

using namespace std;


/// Backtracking and Permutation, Storing by Hash Set
/// Time Complexity: O(n! * n!)
/// Space Complexity: O(n)
class Solution {
public:
    int numTilePossibilities(string tiles) {

        sort(tiles.begin(), tiles.end());
        unordered_set<string> set;
        dfs(tiles, 0, "", set);
        return set.size();
    }

private:
    void dfs(const string& tiles, int index, const string& cur_res, unordered_set<string>& set){

        if(index == tiles.size()){
            if(cur_res != ""){
                string t = cur_res;
                sort(t.begin(), t.end());
                do{
                    set.insert(t);
                }while(next_permutation(t.begin(), t.end()));
            }
            return;
        }

        dfs(tiles, index + 1, cur_res + tiles[index], set);
        dfs(tiles, index + 1, cur_res, set);
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/letter-tile-possibilities/
/// Author : liuyubobobo
/// Time   : 2019-06-15

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>

using namespace std;


/// Counting on the fly, based on frequency of characters
/// Time Complexity: O(n!)
/// Space Complexity: O(n)
class Solution {

public:
    int numTilePossibilities(string tiles) {

        unordered_map<char, int> freq;
        for(char c: tiles)
            freq[c] ++;

        return dfs(freq);
    }

private:
    int dfs(unordered_map<char, int>& freq){

        int res = 0;
        for(char e = 'A'; e <= 'Z'; e ++)
            if(freq[e]){
                res ++;
                freq[e] --;
                res += dfs(freq);
                freq[e] ++;
            }
        return res;
    }
};


int main() {

    cout << Solution().numTilePossibilities("AAB") << endl;
    // 8

    cout << Solution().numTilePossibilities("AAABBC") << endl;
    // 188

    return 0;
}