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 <= 7tiles consists of uppercase English letters.The key idea in #1079 Letter Tile Possibilities is to generate all possible sequences that can be formed using the given letter tiles. Since tiles may contain duplicate characters, a naive permutation approach would generate repeated sequences. A better strategy is to use backtracking with a frequency map.
First, count the occurrences of each character using a HashMap or frequency array. During backtracking, try placing each available character in the current sequence. Each time you choose a character with a positive count, decrease its count, recursively explore further possibilities, and then restore the count (backtrack). Every valid choice contributes to the total number of sequences.
This approach avoids generating duplicate permutations because it tracks remaining counts instead of positions. The overall complexity grows factorially with the number of tiles, but pruning through frequency counting keeps the search manageable.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking with Frequency Count | O(N! ) in the worst case due to exploring permutations | O(N) recursion depth for the call stack |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Try to build the string with a backtracking DFS by considering what you can put in every position.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of permutation and backtracking problems like Letter Tile Possibilities are common in technical interviews, including FAANG companies. They test understanding of recursion, pruning duplicates, and combinatorial search techniques.
Backtracking systematically explores all possible sequences that can be formed from the tiles. By reducing and restoring character counts during recursion, it efficiently generates combinations without repeating identical sequences.
A hash map or fixed-size frequency array works best to store the count of each character. This structure lets you quickly check which tiles are still available and update counts during recursion.
The optimal approach uses backtracking with a frequency count of characters. Instead of generating permutations directly, you track how many of each letter remain and recursively build sequences. This avoids duplicate permutations and efficiently counts all valid sequences.