LeetCode Q 1079 - 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
tiles consists of uppercase English letters.

Solution:

Code:

private Set<String> set;
public int numTilePossibilities(String tiles) {
  set = new HashSet<>();
  int[] count = new int[26];
  for (char ch: tiles.toCharArray()) count[ch - 'A']++;
  backtrack(tiles, new boolean[26], count, "");
  return set.size();
}

private void backtrack(String tiles, boolean[] seen, int[] count, String temp) {
  
  if (temp.length() > 0 && temp.length() <= tiles.length()) {
    set.add(temp);
  }
  
  for (int i = 0; i < tiles.length(); i++) {
    char ch = tiles.charAt(i);
    if (seen[ch - 'A'] && count[ch - 'A'] == 0) 
      continue;
    
    seen[ch - 'A'] = true;
    count[ch - 'A']--;
    backtrack(tiles, seen, count, temp + ch);
    seen[ch - 'A'] = false;
    count[ch - 'A']++;
  }
}

Code: A more efficient version

public int numTilePossibilities(String tiles) {
  int[] count = new int[26];
  for (char ch: tiles.toCharArray()) count[ch - 'a']++;
  return backtrack(count);
}

private void backtrack(int[] count) {
  int sum = 0;

  for (int i = 0; i < 26; i++) {
    if (count[i] == 0) continue;
    count[i]--;
    sum++;
    sum += backtrack(count);
    count[i]++;
  }

  return sum;
}

Reprint policy