NeetCode #496LC-1079MediumBacktracking
← Back to All Problems#496 · #1079 · Letter Tile Possibilities(活字印刷)
📌 Problem Statement & Constraints
You have
n tiles, each with one letter given in tiles. Return the number of possible non-empty sequences of letters you can make. Constraints: 1 <= tiles.length <= 7, uppercase English letters.💡 Core Algorithmic Approaches
- Count the letters, then recursively choose the next letter from those still available.
- Each choice extends the current sequence, so every recursive call beyond the root corresponds to one distinct sequence.
- The count for a node is
1(the current prefix) plus the sum of the children's counts -- but since every non-empty sequence is counted exactly once as a prefix, the standard formulation istotal += 1 + dfs()inside the loop. - Using a frequency map (rather than an index over a sorted list) handles duplicates naturally.
💻 Benchmark Python3 Implementation
class Solution:
def numTilePossibilities(self, tiles: str) -> int:
from collections import Counter
cnt = Counter(tiles)
def dfs() -> int:
total = 0
for ch in cnt:
if cnt[ch] > 0:
cnt[ch] -= 1
total += 1 + dfs() # this prefix + all its extensions
cnt[ch] += 1
return total
return dfs()⚡ Complexity Deep Dive
⏱️ Time Complexity
O(number of sequences) = O(sum over k of P(n, k) / duplicate factorials).
💾 Space Complexity
O(n) for the recursion depth.
⚠️ Interview Pitfalls & Follow-ups
- Generating all permutations of all lengths and deduplicating: exponential waste; the frequency map already handles duplicates.
- Forgetting the
+1for the current prefix: sequences shorter than the maximum length would be missed. - Counting only full-length sequences: every non-empty prefix counts.
- Mutating the counter without restoring it: later branches would see a depleted alphabet.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.