⚡Flashcard Drill➔
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

  1. Count the letters, then recursively choose the next letter from those still available.
  2. Each choice extends the current sequence, so every recursive call beyond the root corresponds to one distinct sequence.
  3. 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 is total += 1 + dfs() inside the loop.
  4. 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 +1 for 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.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems