1079. Letter Tile Possibilities

Posted on Edited on In

1079. Letter Tile Possibilities

Description

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:

1
2
3
Input: tiles = "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

Example 2:

1
2
Input: tiles = "AAABBC"
Output: 188

Example 3:

1
2
Input: tiles = "V"
Output: 1

Constraints:

  • 1 <= tiles.length <= 7
  • tiles consists of uppercase English letters.

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int n;

    int numTilePossibilities(string tiles) {
        n = tiles.size();
        vector<int> count(26, 0);
        for (char& c : tiles) {
            count[c - 'A']++;
        }
        int res = dfs(count);
        return res;
    }

    int dfs(vector<int>& count) {
        int res = 0;

        for (int i = 0; i < 26; i++) {
            if (!count[i]) {
                continue;
            }
            res++;
            count[i]--;
            res += dfs(count);
            count[i]++;
        }
        return res;
    }
};