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.This approach uses backtracking to explore all possible permutations of the tile letters. The permutations are stored in a set to ensure uniqueness, allowing us to retrieve non-duplicate sequences effectively. We recursively select tiles, marking them as used, and backtrack to explore other possibilities.
This solution uses backtracking to explore all possible permutations. We maintain an array called used to check if a tile has been included in the current permutation. If so, it's skipped in further permutations unless it's a unique arrangement. The results are collected into a set to ensure every sequence is unique.
C++
Java
Time Complexity: O(n * n!) where n is the number of tiles, considering permutations with duplicates.
Space Complexity: O(n * n!) for storing the permutations in the set.
This approach utilizes Depth-First Search (DFS) with a frequency map to track the count of each character used, allowing us to construct sequences by branching through available letters. It eliminates duplicate permutations by managing the count of each character carefully.
This solution builds all unique sequences using a frequency map (Counter) and explores different possibilities using a depth-first search mechanism. It examines each possible character by decreasing its availability in the counter, counting each new sequence formed uniquely as characters deplete.
C++
Java
Time Complexity: O(k^n), where k is the number of unique tiles and n is the total number of tiles.
Space Complexity: O(k), primarily due to the stored frequency map.
| Approach | Complexity |
|---|---|
| Backtracking with Set | Time Complexity: O(n * n!) where n is the number of tiles, considering permutations with duplicates. |
| DFS with Frequency Map | Time Complexity: O(k^n), where k is the number of unique tiles and n is the total number of tiles. |
Letter Tile Possibilities - Leetcode 1079 - Python • NeetCodeIO • 11,620 views views
Watch 9 more video solutions →Practice Letter Tile Possibilities with our built-in code editor and test cases.
Practice on FleetCode