Letter Tile Possibilities

• Convert the input tiles string to a character array and sort it. This helps in handling duplicate characters systematically.
• Initialize an empty HashSet<String> to store the unique sequences found.
• Initialize a boolean array visited of the same size as tiles, with all values set to false, to keep track of which tile indices have been used in the current sequence.
• Define a recursive helper function, let's call it dfs, that builds the sequences.
• The dfs function iterates through the sorted character array. For each character:
  • It checks if the character at the current index has already been visited. If so, it skips to the next one.
  • To avoid generating duplicate permutations (e.g., from "AAB"), it includes a crucial check: if the current character is the same as the previous one (tiles[i] == tiles[i-1]) and the previous one has not been visited (!visited[i-1]), it skips the current character. This ensures that for a group of identical characters, they are always picked in order.
  • If the character can be used, it's appended to the current sequence being built (e.g., a StringBuilder).
  • The newly formed sequence is added to the HashSet.
  • The character's index is marked as visited.
  • A recursive call is made to dfs to continue building longer sequences.
  • After the recursive call returns (backtracking), the last character is removed from the sequence builder, and the visited status is reset to false.
• The initial call is made to this dfs function.
• Finally, the size of the HashSet is returned, which represents the total number of unique non-empty sequences.

The core of this method is a recursive backtracking function. To handle duplicate letters in the input tiles (like in "AAB"), we first sort the tiles string. This groups identical letters together, making them easier to manage.

The backtracking function, let's call it dfs, builds sequences character by character. It uses a boolean visited array to keep track of which tiles have been used in the current path. In each recursive step, it iterates through the tiles. If a tile hasn't been visited, it appends it to the current sequence, adds this new sequence to a HashSet, marks the tile as visited, and then calls itself to extend the sequence further.

The key to handling duplicates lies in a specific condition: if the current tile is identical to the previous one and the previous one was not used in the current path (i.e., we have backtracked past it), we skip the current tile. This pruning strategy prevents the algorithm from starting new paths with the second 'A' that are identical to paths already generated with the first 'A', thus avoiding duplicate permutations.

After a recursive call returns, the function backtracks by undoing its last choice—removing the character from the sequence and un-marking it as visited. This allows the exploration of other possibilities. The total count is the final size of the HashSet.

1import java.util.Arrays;2import java.util.HashSet;3import java.util.Set;4 5class Solution {6    public int numTilePossibilities(String tiles) {7        char[] chars = tiles.toCharArray();8        Arrays.sort(chars);9        Set<String> resultSet = new HashSet<>();10        boolean[] visited = new boolean[chars.length];11        dfs(new StringBuilder(), chars, visited, resultSet);12        return resultSet.size();13    }14 15    private void dfs(StringBuilder currentPath, char[] tiles, boolean[] visited, Set<String> resultSet) {16        for (int i = 0; i < tiles.length; i++) {17            if (visited[i]) {18                continue;19            }20            // This is the key condition to avoid duplicate permutations.21            // If the current character is the same as the previous one,22            // and the previous one has not been picked in this path,23            // skip the current character to avoid redundant computations.24            if (i > 0 && tiles[i] == tiles[i - 1] && !visited[i - 1]) {25                continue;26            }27 28            visited[i] = true;29            currentPath.append(tiles[i]);30            31            resultSet.add(currentPath.toString());32            dfs(currentPath, tiles, visited, resultSet);33            34            // Backtrack35            currentPath.deleteCharAt(currentPath.length() - 1);36            visited[i] = false;37        }38    }39}

• First, create a frequency map of the characters in the input tiles string. An integer array of size 26 is suitable for this, where counts[0] stores the count of 'A', counts[1] for 'B', and so on.
• Define a recursive helper function, dfs(counts), that calculates and returns the number of unique sequences possible with the given character counts.
• Inside the dfs function, initialize a local counter sum to 0.
• Iterate through the frequency map from i = 0 to 25.
• For each index i, if counts[i] is greater than 0, it means the character corresponding to i is available.
  • Increment sum. This counts the single-character sequence formed by this character.
  • Decrement counts[i] to signify that one instance of this character has been used.
  • Make a recursive call dfs(counts) to find all sequences that can be formed by appending to the character just chosen. Add the returned value to sum.
  • Backtrack by incrementing counts[i] back to its previous value. This restores the state for exploring other possibilities (e.g., sequences starting with a different character).
• The dfs function returns the total sum.
• The final answer is the result of the initial call to dfs with the frequency map of the original tiles string.

This method transforms the problem from generating permutations of tiles to counting combinations of character frequencies.

1. Frequency Count: We begin by iterating through the tiles string once to populate a frequency array, say counts, of size 26. For tiles = "AAB", this array would be [2, 1, 0, ..., 0], indicating two 'A's and one 'B'.

2. Recursive Counting: We define a recursive function, dfs(counts), that calculates the number of unique sequences that can be formed from the available characters represented by the counts array.

Inside dfs, we loop through our counts array. If counts[i] for a character i is positive, we know we can form at least one new sequence starting with this character. So, we increment our result counter. Then, to find all sequences that extend this one, we decrement counts[i] (as if we've used one instance of that character) and make a recursive call dfs(counts). The result of this call is the number of ways to complete the sequence, which we add to our total.

3. Backtracking: After the recursive call returns, we must restore the state by incrementing counts[i] back. This is the backtracking step, ensuring that the character is available again for other recursive paths (e.g., for sequences that don't start with this character).

The final result is the sum of possibilities explored in the initial dfs call. This method is highly efficient because the state of the recursion is just the small counts array, and we never perform costly string operations or store large collections.

1class Solution {2    public int numTilePossibilities(String tiles) {3        int[] counts = new int[26];4        for (char c : tiles.toCharArray()) {5            counts[c - 'A']++;6        }7        return dfs(counts);8    }9 10    private int dfs(int[] counts) {11        int sum = 0;12        for (int i = 0; i < 26; i++) {13            if (counts[i] == 0) {14                continue;15            }16            // Count the new sequence formed by picking this character.17            sum++;18            19            // Use one character.20            counts[i]--;21            22            // Recursively count sequences that can be formed with the rest.23            sum += dfs(counts);24            25            // Backtrack to restore the count for other possibilities.26            counts[i]++;27        }28        return sum;29    }30}