Depth First Search to Compute the Permutation with Duplicates: Letter Tile Possibilities

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

Permutation via Depth First Search Algorithm and Hash Set

This is a permutation problem where the duplicates are not counted. Thus, we can use the hash set to record only the unique tiles/permutations. We can use the DFS (Depth First Search) algorithm that takes the result hash set, the current available tiles, and the current possible permutation, and the maximum tile length as parameters.

If the current permutation length is less than the maximum, we can add the string to the hash set. Also, the next tile could be any of the available tiles, and when we recursively call the DFS function, we need to take the current tile out.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int numTilePossibilities(string tiles) {
        unordered_set<string> r;
        dfs(r, tiles, "", tiles.size());
        return r.size();
    }
    
private:
    void dfs(unordered_set<string> &result, string tiles, string cur, int n) {        
        if (cur.size() <= n && cur != "") {
            result.insert(cur);
        }
        for (int i = 0; i < tiles.size(); ++ i) {
            dfs(result, tiles.substr(0, i) + tiles.substr(i + 1), cur + tiles[i], n);
        }
    }
};

class Solution {
public:
    int numTilePossibilities(string tiles) {
        unordered_set<string> r;
        dfs(r, tiles, "", tiles.size());
        return r.size();
    }
    
private:
    void dfs(unordered_set<string> &result, string tiles, string cur, int n) {        
        if (cur.size() <= n && cur != "") {
            result.insert(cur);
        }
        for (int i = 0; i < tiles.size(); ++ i) {
            dfs(result, tiles.substr(0, i) + tiles.substr(i + 1), cur + tiles[i], n);
        }
    }
};

Lastly, we need to return the size of the hash set. The space complexity is O(N) (maximum depth of recursion) and the time complexity is O(N^2) via recursion.

–EOF (The Ultimate Computing & Technology Blog) —