Letter Tile Possibilities LeetCode solution in C++

1
/*
2
                    h( AAB , -1 , 0 )              LEVEL=0 ie 0 length substring
3
                    /               \
4
            h('A'AB,0,1)           h('B'AA,6,1)    LEVEL=1 ie 1 length
5
   substrings ("A","B") /         \              / h('AA'B,1,2) h('AB'A,4,2)
6
   h('BA'A,7,2)     LEVEL=2 ie 2 length substrings ("AB","BA","AA") / / /
7
    h('AAB',2,3)    h('ABA',5,2)  h('BAA',8,3)     LEVEL=3 ie 3 length
8
   substrings
9
                                                   ("AAB", "ABA", "BAA")
10
*/
11
class Solution {
12
  void backtrack(string tiles, int level, int &count) {
13
    count++;
14
    for (int i = level; i < tiles.length(); i++) {
15
      if (i != level && tiles[i] == tiles[level]) continue; // to skip same characters
16
      swap(tiles[i], tiles[level]);
17
      backtrack(tiles, level + 1, count);
18
    }
19
  }
20

21
 public:
22
  int numTilePossibilities(string tiles) {
23
    int count = -1;
24
    sort(tiles.begin(), tiles.end());
25

26
    backtrack(tiles, 0, count); // level = susbstring length
27

28
    return count;
29
  }
30
};