1079. Letter Tile Possibilities

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:

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

Example 2:

Input: tiles = "AAABBC"
Output: 188

Example 3:

Input: tiles = "V"
Output: 1

 Constraints:

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

JAVA

• class Solution {
      public int numTilePossibilities(String tiles) {
          int[] cnt = new int[26];
          for (char c : tiles.toCharArray()) {
              ++cnt[c - 'A'];
          }
          return dfs(cnt);
      }
  
      private int dfs(int[] cnt) {
          int res = 0;
          for (int i = 0; i < cnt.length; ++i) {
              if (cnt[i] > 0) {
                  ++res;
                  --cnt[i];
                  res += dfs(cnt);
                  ++cnt[i];
              }
          }
          return res;
      }
  }

C++

• class Solution {
  public:
      int numTilePossibilities(string tiles) {
          int cnt[26]{};
          for (char c : tiles) {
              ++cnt[c - 'A'];
          }
          function<int(int* cnt)> dfs = [&](int* cnt) -> int {
              int res = 0;
              for (int i = 0; i < 26; ++i) {
                  if (cnt[i] > 0) {
                      ++res;
                      --cnt[i];
                      res += dfs(cnt);
                      ++cnt[i];
                  }
              }
              return res;
          };
          return dfs(cnt);
      }
  };

PYTHON

• class Solution:
      def numTilePossibilities(self, tiles: str) -> int:
          cnt = [0] * 26
          for c in tiles:
              cnt[ord(c) - ord('A')] += 1
          return self.dfs(cnt)
  
      def dfs(self, cnt):
          res = 0
          for i in range(26):
              if cnt[i] > 0:
                  res += 1
                  cnt[i] -= 1
                  res += self.dfs(cnt)
                  cnt[i] += 1  # Backtrack
          return res