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:


Solution:

class Solution {
    public int numTilePossibilities(String tiles) {
        char[] arr = tiles.toCharArray();
        Set<String> set = new HashSet();
        helper(arr, 0, set, new StringBuilder());
        // System.out.println(set);
        return set.size();
    }
    
    private void helper(char[] arr, int i, Set<String> set, StringBuilder sb) {
        if (i == arr.length) {
            if (sb.length() > 0) {
                set.add(sb.toString());
            }
            return;
        }
        for (int j = i; j < arr.length; j ++) {
            swap(arr, i, j);
            helper(arr, i + 1, set, sb);
            sb.append(arr[i]);
            helper(arr, i + 1, set, sb);
            sb.deleteCharAt(sb.length() - 1);
            swap(arr, i, j);
        }
    }
    
    private void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Thoughts


input: AAB
count: A -> 2, B -> 1


For sequence of length 1:



For sequence of length 2:



For sequence of length 3: blablabla


Implementation


  1. We don't need to keep track of the sequence. We only need count
  2. If we implement the above idea by each level (Count all sequence of length 1, then count all sequence of length 2, etc), we have to remember previous sequence.
  3. So we use recursion instead. Just remember to add the count back (arr[i]++).

    public int numTilePossibilities(String tiles) {
        int[] count = new int[26];
        for (char c : tiles.toCharArray()) count[c - 'A']++;
        return dfs(count);
    }
    
    int dfs(int[] arr) {
        int sum = 0;
        for (int i = 0; i < 26; i++) {
            if (arr[i] == 0) continue;
            sum++;
            arr[i]--;
            sum += dfs(arr);
            arr[i]++;
        }
        return sum;
    }