1079. Letter Tile Possibilities - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

You have a set of n letter tiles, each with a letter printed on it. You can arrange some or all of these tiles in any order to form sequences (like forming words from letters). The task is to count the number of distinct non-empty sequences you can form using these tiles, where each tile can be used at most once in a sequence. Order matters in these sequences (so "AB" and "BA" are considered different). You may use any number of tiles from 1 up to n (use all tiles or just a subset), as long as the sequence is not empty.

Example 1:
Input: tiles = "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA". There are 8 distinct sequences in total.
Example 2:
Input: tiles = "AAABBC"
Output: 188
Explanation: (There are 188 unique sequences that can be formed; listing them is impractical, but the count is 188.)
Example 3:
Input: tiles = "V"
Output: 1
Explanation: With only one tile "V", the only sequence you can form is "V" itself.

Constraints:

1 <= tiles.length <= 7
tiles consists of uppercase English letters (A–Z).
There can be duplicate letters in tiles. The output can be large but will fit in a standard integer due to the small max length (for length 7, the maximum number of sequences is not extremely high).

What is Being Asked: We need to compute the count of all distinct sequences (permutations of any length) that can be formed from the given multiset of letters. We are not required to list all sequences, only to count them. We must ensure not to count any sequence more than once, especially when there are duplicate letters.

Hints

Think in Terms of Permutations: If all tiles had distinct letters, this would be a simpler permutation problem – we would generate all permutations of all possible lengths (1 through n). But with possible duplicates, many permutations repeat. How can you avoid counting duplicates more than once? Consider using a strategy to handle repeating letters.
Use Recursion/Backtracking: Try to build sequences one letter at a time. You can choose any unused tile as the next letter in the sequence. This suggests a recursive (backtracking) approach where at each step you pick one of the remaining letters to append to the current sequence.
Track Used Letters: To manage duplicates, it might help to keep track of how many of each letter you have left. For example, if you have "AAB", you have 2 A tiles and 1 B tile. If you use one A, you'll have 1 A left for further choices. A frequency count or boolean array of used tiles can be useful.
Avoid Duplicate Paths: If you generate sequences by picking tiles, you need to ensure that using the first A vs the second A (when tiles are identical) doesn't count as two different sequences. Think about how you can structure your recursion or iteration to skip over duplicate letters in the same position. (One hint: sorting the letters and skipping adjacent duplicates is one way to do this in permutations problems.)

Multiple Approaches

Brute Force Approach

Idea: Generate all possible sequences by trying every arrangement of the tiles, and use a data structure to ensure uniqueness. A brute force method would be:

Produce every permutation for every possible length from 1 to n. This can be done with recursion by trying each tile as the next letter.
Because duplicate letters can lead to the same sequence generated multiple times, use a set to collect sequences and avoid counting duplicates multiple times.
In the end, the size of the set will be the number of distinct sequences.

Explanation: We treat it as generating all permutations of all lengths. For each starting tile, explore all arrangements of the remaining tiles, and so on. Every time we form a sequence (of any length), we add it to a set. The set takes care of filtering out duplicates automatically (since sets only keep unique entries). This approach is straightforward but can be inefficient because it may generate the same sequence many times via different paths (especially when there are duplicates). However, given the constraint of at most 7 tiles, this brute force approach can still run in a reasonable time (the total number of sequences is not astronomically large for n=7).

Steps:

Recursively build sequences: Pick any tile as the first letter, then recursively pick another from the remaining tiles for the second letter, and so on. You can stop at any point and record the sequence formed.
Use a set for unique sequences: Keep a global set. Every time you form a new sequence (at least 1 letter long), insert it into the set. This will ensure that if the same sequence is formed via different paths (which can happen if there are identical letters), it is only counted once.
Generate all lengths: The recursion naturally generates sequences of all lengths. For example, it will generate all 1-letter sequences, all 2-letter sequences, etc., because you don't always have to use all tiles. (You can stop the recursion at different depths.)
Return the count: After exploring all possibilities, the answer is just the size of the set.

Let's illustrate the brute force with a short example:

If tiles = "AB", the recursion will generate: "A", then "AB"; and "B", then "BA". The set will contain {"A","AB","B","BA"} and the count is 4.
If tiles = "AA", the recursion might generate "A" twice (once for each choice of A tile) and "AA" once, but the set will end up with {"A","AA"} so the count is 2, correctly handling the duplicate.

Brute Force Code (Python): Using recursion and a set to accumulate unique sequences.

Python3

. . . .

In this code, backtrack(current_seq, remaining_tiles) picks each possible next letter from remaining_tiles and recurses. We add current_seq to the set whenever it's non-empty. The use of a set ensures duplicates are filtered out. This brute force will indeed generate sequences multiple times if there are duplicate letters (for instance, two "A" tiles lead to the same sequence paths), but the set keeps only unique ones.

Complexity Analysis (Brute Force): This approach explores all permutations of all subsets of the tiles. In the worst case with all distinct letters, it generates roughly $\sum_{k=1}^{n} P(n,k)$ sequences (permutations of length 1 up to n). This is less than $n! \cdot n$ but grows factorially with n. Big-O wise, the time complexity is O(n * n!) in the worst case (which for $n=7$ is manageable) since for each permutation we also handle joining strings and set operations. Handling duplicates doesn't reduce the attempted permutations, but the set insertion ensures we don't double count. Space complexity is high: in worst case we could store all unique sequences. That could be up to ~14,000 sequences for n=7 distinct letters (for example, 7 distinct letters produce 13,699 sequences total as we calculated), so roughly O(n * n!) space in the worst case for the set. The recursion stack goes at most depth n (so O(n) additional stack space). Because n is at most 7, this brute force is feasible, but it's not optimal.

Optimized Approach (Backtracking with Counting)

Idea: Instead of generating duplicate sequences and filtering them out, we can directly avoid generating duplicates by using a count of available letters and a depth-first search (DFS) recursion. The optimization comes from not distinguishing between identical tiles – we treat them as one group. We use a frequency map (or array of size 26 for letters) to keep track of how many of each letter remain. At each step of recursion, we try to use one of each distinct available letter, reducing its count, and recursively build further sequences. This way, each unique sequence is constructed once.

Key Insight: When you choose a letter to add next, if there are multiple tiles of that letter available, choosing any one of them leads to the same outcome. So treat them as one choice (decrement the count). By iterating over distinct letters, you inherently skip over generating the same sequence starting with the same letter multiple times. This eliminates the need for a set to avoid duplicates, resulting in fewer recursive calls.

Steps:

Count the Tiles: First count the occurrences of each letter in the input. For example, "AAB" would give a count map like {A: 2, B: 1}. We can use an array of length 26 (index 0 for 'A', 1 for 'B', etc.) or a dictionary for the counts.
DFS Recursion: Define a recursive function dfs(count_map) that returns the number of sequences that can be formed with the given remaining letter counts. In each call:
- Initialize a local counter (for sequences from this state) to 0.
- Loop over each letter L from 'A' to 'Z' (or each key in the count map):
  - If count_map[L] is greater than 0 (meaning that letter is available to use):
    - Use that letter: decrement count_map[L] by 1 (consume one tile of L).
    - This use of a letter forms a new sequence (appending L to the current prefix), so increment the counter by 1 (count the sequence formed by just adding this letter now).
    - Recur by calling dfs with the updated counts to count all longer sequences starting with this prefix letter. Add the result of recursion to the counter.
    - Backtrack: increment count_map[L] back by 1 to restore the count (so other branches can use that tile).
- Return the counter.
Compute Result: Call dfs with the full count map initially. This will count all sequences. The result of this call is the total number of sequences possible.

Explanation: Each call of dfs tries adding one of the available letters next. The moment we add a letter, we count that as one valid sequence (this corresponds to the current prefix ending here) and then continue to build longer sequences from that prefix. This way, every distinct sequence is counted exactly once. We do not generate any sequence twice because once a letter count is 0, we skip it, and we never consider two identical letters as separate choices at the same level — they are one choice due to using the count. This is essentially a backtracking search through the space of sequences, treating identical letters as indistinguishable choices to avoid duplicate sequences.

Using the example "AAB" ({A:2, B:1}):

At the start, dfs({A:2, B:1}) will try letter 'A' and letter 'B' in the loop.
Choosing 'A': decrement count to {A:1, B:1}, count +1 for sequence "A". Recurse dfs({A:1, B:1}) to count sequences that start with "A".
Inside that, again try 'A' (available 1) and 'B'.
- 'A': decrement to {A:0, B:1}, count +1 for sequence "AA". Recurse dfs({A:0, B:1}).
  - Try 'A' (skip, count 0 now), try 'B': decrement to {A:0, B:0}, count +1 for "AAB". Recurse dfs({A:0, B:0}) which returns 0 (no more letters). Backtrack B.
  - Return from this call with count for sequences starting "AA" (which were "AA" and "AAB").
- 'B': (back at prefix "A") decrement to {A:1, B:0}, count +1 for "AB". Recurse dfs({A:1, B:0}).
  - Try 'A': decrement to {A:0, B:0}, count +1 for "ABA". Recurse returns 0. Backtrack A.
  - (No 'B' to try, since B count 0.) Return count for sequences starting "AB".
- Backtrack the usage of 'A' and 'B' at prefix "A".
Now choose 'B' at the start: decrement to {A:2, B:0}, count +1 for "B". Recurse dfs({A:2, B:0}) to count sequences starting with "B".
- Try 'A': decrement to {A:1, B:0}, count +1 for "BA". Recurse dfs({A:1, B:0}).
  - Try 'A': decrement to {A:0, B:0}, count +1 for "BAA". Recurse returns 0. Backtrack A.
  - Return count for sequences starting "BA".
- (No 'B' to try since B count 0.) Backtrack and return.
Summing all these counted sequences yields 8, as expected.

This approach avoids generating any particular sequence more than once. We directly count each unique sequence in the recursion.

Optimized Code (Python): Using a frequency counter and DFS/backtracking.

Python3

. . . .

In this code, we use Python's Counter to store letter frequencies. We iterate over each letter with a non-zero count and treat it as the next letter in the sequence. We decrement the count, count one sequence (the new prefix), then recurse deeper. After recursion, we increment the count back. This dfs returns the number of sequences possible from that state, and we accumulate it in total. Finally, the top-level call returns the total number of sequences. This matches the logic described above.

(Alternatively, one can implement the same logic with an array of size 26 for counts. The idea is identical, just the implementation differs. Many official solutions use an integer array for speed, since the alphabet is fixed size .)

Complexity Analysis (Optimized DFS Approach): The time complexity is exponential, but more precisely it is bounded by the number of distinct sequences that can be formed. Each unique sequence is generated once. In the worst case of all distinct letters, this is $\sum_{k=1}^{n} P(n, k)$ , which is $O(n!)$ (factorial) in magnitude. For n=7, this is on the order of 10,000+ operations at most. If there are duplicates, the number of sequences (and thus recursive calls) is less. So we can say the time complexity is O(N!) in the worst case (factorial growth with the number of tiles). The space complexity is O(n) for recursion stack plus the frequency data structure. We do not store all sequences explicitly (we count on the fly), so we save memory compared to the brute force. Only the count map and recursion stack use space; the count map is size 26 at most, and recursion depth is at most n (7). Thus space is O(26 + n), which is O(1) w.r.t n (or O(n) if considering n itself is small).

Comparison of Approaches

The brute force approach is easier to implement (just generate everything and use a set) but does unnecessary work by generating duplicate sequences multiple times. Its time complexity is effectively factorial and it also uses extra memory to store all sequences.
The optimized backtracking approach avoids generating duplicates by design. It is also factorial time in the worst case, but it prunes a lot of redundant calls. It uses much less extra memory (only counters and recursion stack) since we don't keep a large result list or set.
Both approaches will produce correct results for n up to 7. For larger n, the brute force would become infeasible much faster due to explosive growth and memory usage, whereas the optimized approach would handle it a bit more gracefully (but even optimized, for significantly large n, the count of sequences would be huge).

Step-by-Step Walkthrough of Optimal Solution

Let's walk through the optimal backtracking approach using a concrete example to see how it counts sequences. Consider tiles = "AAB". The distinct letters are A and B with counts {A:2, B:1}. We will trace the recursive calls and counts. We maintain a prefix (the sequence built so far) and the remaining counts of tiles at each step. Every time we choose a letter, we count a new sequence.

For clarity, we'll tabulate the process:

Current Prefix	Remaining Counts (A, B)	Action & New Sequence Counted
`""` (empty)	A:2, B:1	Start: No sequence yet. Can choose `A` or `B` as next letter.
`"A"`	A:1, B:1	Chose A as first letter. Count "A" as a valid sequence.
`"AA"`	A:0, B:1	Chose A again. Count "AA" as a valid sequence.
`"AAB"`	A:0, B:0	Chose B. Count "AAB" as a valid sequence. (Now no tiles remain.)
(backtrack)	A:0, B:1	Backtrack from `"AAB"` to prefix `"AA"`. (Restore B count to 1.) `"AA"` has no other letters to try (A count is 0, B was tried).
(backtrack)	A:1, B:1	Backtrack from `"AA"` to prefix `"A"`. (Restore A count to 1.) Now at prefix `"A"`, next try the other letter `B`.
`"AB"`	A:1, B:0	Chose B as second letter (prefix was "A"). Count "AB" as a valid sequence.
`"ABA"`	A:0, B:0	Chose A. Count "ABA" as a valid sequence. (No tiles remain.)
(backtrack)	A:1, B:0	Backtrack from `"ABA"` to prefix `"AB"`. (Restore A count to 1.) `"AB"` has no other letter to try (B count is 0 now).
(backtrack)	A:2, B:1	Backtrack from `"AB"` to prefix `""` (empty). (Restore B count to 1.) We finished all sequences starting with `"A"`. Now try starting with B.
`"B"`	A:2, B:0	Chose B as first letter. Count "B" as a valid sequence.
`"BA"`	A:1, B:0	Chose A. Count "BA" as a valid sequence.
`"BAA"`	A:0, B:0	Chose A again. Count "BAA" as a valid sequence. (No tiles remain.)
(backtrack)	A:1, B:0	Backtrack from `"BAA"` to prefix `"BA"`. (Restore A count to 1.) `"BA"` has no other letter to try.
(backtrack)	A:2, B:0	Backtrack from `"BA"` to prefix `"B"`. (Restore A count to 2.) `"B"` has no other letter to try (B count is 0).
(backtrack)	A:2, B:1	Backtrack from `"B"` to prefix `""`. (Restore B count to 1.) All possibilities are now exhausted.

Now let's list all the sequences we counted in the order they were found: "A", "AA", "AAB", "AB", "ABA", "B", "BA", "BAA". That’s 8 sequences, which matches the expected result. Notice that each sequence appeared exactly once in our process. The algorithm systematically went through all unique combinations:

Starting with "A" (then explored "AA" -> "AAB", and "AB" -> "ABA"),
Then starting with "B" (then "BA" -> "BAA").

The backtracking steps (where we restore counts and step back up) ensure that after finishing all sequences that start with a certain prefix, we try a different letter for that prefix or backtrack further. By using counts, we never tried to start with the second "A" as a separate case — doing so would have produced the same results as starting with the first "A", so it was unnecessary. This is how the duplicate sequences are avoided.

Python and Java Implementations

Python Implementation

Python3

. . . .

Explanation: The function numTilePossibilities uses a Counter to track available tiles and a nested dfs function to explore possibilities. In the main section, we call the function on sample inputs to verify it returns the expected counts.

Java Implementation

Java

. . . .

Explanation: The Java solution uses an array count[26] to store counts of 'A' through 'Z'. The dfs method tries to use each letter (if available) and recursively counts further sequences. The main method tests the function with the given examples, printing the results. (In a LeetCode environment, only the numTilePossibilities method and dfs would be inside the Solution class, and the testing would be separate.)

Complexity Analysis of Each Approach

Brute Force Approach: Time complexity is on the order of $O(n \times n!)$ (factorial growth) in the worst case, because it generates every permutation of every subset of letters. This is exponential. Space complexity is also high, up to $O(n \times n!)$ to store all sequences in the worst case (when all letters are distinct and thus all permutations are unique). However, with $n \le 7$ , the absolute number of sequences is at most a few thousand.
Optimized DFS Approach: Time complexity is $O(n!)$ in the worst case . The algorithm still potentially explores all unique sequences (which is inherently factorial). The pruning of duplicate branches makes it much more efficient than brute force when there are duplicates, but Big-O is still factorial with respect to n. Space complexity is $O(n)$ for recursion depth and count storage, plus O(26) which is constant. We are not storing all sequences, just counting, so memory usage is modest.

(Note: In terms of Big-O, both approaches are exponential. The problem intrinsically requires exploring a combinatorial number of sequences. The optimized approach significantly reduces the constant factors by avoiding redundant exploration.)

Common Mistakes and Pitfalls

Counting the Empty Sequence: A frequent mistake is to include the empty sequence in the count. The problem specifically asks for non-empty sequences. Ensure that your counting starts when you pick at least one tile. In the recursive approach, notice we only count after we choose a letter (which guarantees the sequence length is at least 1).
Double Counting Due to Duplicates: Not handling duplicate letters properly can lead to counting the same sequence multiple times. For example, if you have two 'A's, treating them as distinct in generation will produce duplicate sequences. A mistake would be not skipping or not using a set in the brute force approach, or not managing the frequency counts correctly in the optimized approach. Always ensure identical letters are either grouped (frequency count) or skipped in recursion to avoid double counting.
Forgetting to Backtrack (Restore State): In the backtracking solution, a common bug is forgetting to restore the count of a letter after the recursive call. If you decrement a count and don't increment it back, it corrupts the state for subsequent calls. The same goes for approaches that use a boolean array of used tiles – you must mark a tile as used and then mark it as unused when backtracking.
Using Permutation Formula Incorrectly: Some might attempt to use mathematical formulas (like factorials and combinations) to calculate the count directly. This can get complicated due to having to sum over all subset lengths and adjust for duplicate letters. It's easy to make an error in these calculations. For instance, one user tried a formula-based approach and got the wrong result for a case with many duplicates ("AAABBC" was giving 164 instead of 188) . Generally, it's safer to use backtracking to systematically count rather than closed-form formulas for this problem.
Misinterpreting the Problem (Order vs Combination): Sometimes people confuse this with a combinations problem and might only count unique sets of letters, ignoring order. Remember that "ABA" and "AAB" are different sequences even though they use the same multiset of letters. The problem is about sequences (permutations), not combinations of letters. Ensure your approach accounts for arrangement order.

Edge Cases

Consider these edge cases and ensure your solution handles them:

Single Tile: If there is only one tile, e.g. "V", the answer should be 1 (only the sequence consisting of that single letter). Make sure the code returns 1 and not 0. The recursion should count a single-letter sequence properly.
All Tiles Identical: If all letters are the same, e.g. "AAAA", then you cannot form different permutations by reordering (they all look the same sequence of A's). The only distinct sequences are "A", "AA", "AAA", ... up to the full length. For input of k identical letters, the answer should be k (because using 1,2,...,k of them gives distinct sequences). Our backtracking solution naturally handles this: each recursion depth you either take another letter (if any left). For example, "AAAA" yields sequences: "A", "AA", "AAA", "AAAA" (4 sequences). This is a good test to ensure no over-counting.
All Tiles Distinct: If all letters are different (e.g. "ABC"), the number of sequences is the sum of all permutations of length 1, 2, ..., n. For "ABC", that is 3 + 6 + 6 = 15. The algorithm should generate all of them. This is a scenario with maximum sequences. Ensure performance is still fine (which it should be for n=7 max).
Some Duplicate, Some Unique: Mixed cases like "AAB" or "AABC" to ensure the approach counts properly. These are normal cases, but it's important to verify the sequence counting logic in these scenarios (we saw "AAB" in detail).
Case Sensitivity or Input Validation: The problem specifies uppercase letters and at least 1 tile, so we don't have to handle lowercase or empty input. If implementing generally, one might consider normalization of input or handling empty string as a special case (which would result in 0 sequences, but here empty input isn't allowed by constraints).

Alternative Variations of the Problem

This problem can be seen as a variant of generating permutations of a multiset of characters, but with the twist of allowing sequences shorter than the full length. Some variations or related scenarios:

Listing All Sequences: Instead of just counting, a variation could ask to return all possible sequences that can be formed from the tiles. This would require generating and storing potentially thousands of strings. The approach would be similar (backtracking) but you would collect results in a list rather than counting. For large n, this would be impractical to output, but for small n it could be done.
Exact Length Sequences: Another variation could be to count or list sequences of exactly a certain length k (1 ≤ k ≤ n) from the given tiles. You would then adjust the recursion to only count when a sequence reaches length k, or stop recursion beyond that length.
Unlimited Tile Usage: A different twist could be if you could reuse tiles (like if you had infinite supply of those letters, or a certain number of each letter but you could use less or more). That would turn it into a different combinatorial problem (possibly infinite if reuse is unlimited without length bound, or a bounded combinatorics problem if a length is specified).
Words in Dictionary: A practical variation is checking how many valid words (from a dictionary) can be formed from given tiles (like a Scrabble helper). That would incorporate an additional constraint of the sequence having to be a real word.
Permutations of Multiset: The classic related problem is to count (or generate) all distinct permutations of all the tiles using all tiles. That is actually simpler than this problem, because you only consider full-length permutations. The count for that can be computed with factorials divided by duplicate counts (e.g. for "AAB", full-length permutations = 3! / (2! * 1!) = 3). Our problem extends this by considering all subset lengths, which makes a direct formula more complicated, hence the recursive solution.
Combinations vs Permutations: One could also consider combinations (where order doesn't matter). For example, "AAB" combinations of any length (ignoring order) would be {"A", "B", "AA", "AB", "AAB"} – but that is a different question entirely. It’s worth understanding the difference: our problem is permutations (arrangements) count.

These variations require similar backtracking techniques or combinatorial reasoning with adjustments for the specific requirements.

If you found this problem interesting, here are some related problems and topics that involve combinatorial generation and backtracking:

Permutations (LeetCode 46): Given a list of distinct numbers, generate all permutations. This is simpler (no duplicates handling needed) and is a good introduction to backtracking.
Permutations II (LeetCode 47): Given a list of numbers that may contain duplicates, return all unique permutations. This is directly related in that you must handle duplicate elements when generating permutations (very similar to handling duplicate letters in tiles).
Subsets (LeetCode 78) and Subsets II (LeetCode 90): These ask for all subsets of a set (or multiset) of numbers. Subsets are combinations (order doesn't matter) rather than permutations, but the "Subsets II" problem involves avoiding duplicate subsets when input has duplicates – a similar challenge of skipping over duplicate choices.
Letter Combinations of a Phone Number (LeetCode 17): Although a different scenario, it involves generating all combinations of letters given digit to letter mappings (backtracking approach). It helps practice generating combinations of characters.
Generate Parentheses (LeetCode 22): Another backtracking problem where you generate all valid strings of balanced parentheses of a certain length. It’s a different kind of sequence generation, but it strengthens understanding of backtracking with constraints.
Anagrams and Word Permutation problems: There are problems where you must check if two strings are anagrams, or find all anagrams of a string in another string, etc. These are related by the concept of permutations of letters. Counting or generating permutations of tiles is like generating anagrams of all lengths.

1079. Letter Tile Possibilities - Detailed Explanation

Problem Statement

Hints

Multiple Approaches

Brute Force Approach

Optimized Approach (Backtracking with Counting)

Comparison of Approaches

Step-by-Step Walkthrough of Optimal Solution

Python and Java Implementations

Python Implementation

Java Implementation

Complexity Analysis of Each Approach

Common Mistakes and Pitfalls

Edge Cases

Alternative Variations of the Problem

Related Problems for Further Practice