Skip to content

1079. Letter Tile Possibilities 👍

  • Time: $O(n^{26})$
  • Space: $O(n)$
 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 numTilePossibilities(string tiles) {
    vector<int> count(26);

    for (const char t : tiles)
      ++count[t - 'A'];

    return dfs(count);
  }

 private:
  int dfs(vector<int>& count) {
    int possibleSequences = 0;

    for (int& c : count) {
      if (c == 0)
        continue;
      // Put c in the current position. We only care about the number of
      // possible sequences of letters but don't care about the actual
      // combination.
      --c;
      possibleSequences += 1 + dfs(count);
      ++c;
    }

    return possibleSequences;
  }
};

 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
class Solution {
  public int numTilePossibilities(String tiles) {
    int[] count = new int[26];

    for (final char t : tiles.toCharArray())
      ++count[t - 'A'];

    return dfs(count);
  }

  private int dfs(int[] count) {
    int possibleSequences = 0;

    for (int i = 0; i < 26; ++i) {
      if (count[i] == 0)
        continue;
      // Put c in the current position. We only care about the number of possible
      // sequences of letters but don't care about the actual combination.
      --count[i];
      possibleSequences += 1 + dfs(count);
      ++count[i];
    }

    return possibleSequences;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def numTilePossibilities(self, tiles: str) -> int:
    count = collections.Counter(tiles)

    def dfs(count: dict[int, int]) -> int:
      possibleSequences = 0

      for k, v in count.items():
        if v == 0:
          continue
        # Put c in the current position. We only care about the number of possible
        # sequences of letters but don't care about the actual combination.
        count[k] -= 1
        possibleSequences += 1 + dfs(count)
        count[k] += 1

      return possibleSequences

    return dfs(count)