LeetCode 1079: Letter Tile Possibilities

Problem Restatement

We have a set of tiles with letters on them.

We need to return the number of possible non-empty sequences of letters using some or all of the tiles.

Two sequences are the same if they use the same letters in the same order.

The official constraints state that 1 <= tiles.length <= 7 and each tiles[i] is an uppercase English letter.

Input and Output

Function shape:

def numTilePossibilities(tiles: str) -> int:
    ...

Examples

Example 1:

tiles = "AAB"

Possible sequences: A, B, AA, AB, BA, AAB, ABA, BAA.

Answer:

8

Key Insight

Use backtracking with a frequency count of each letter.

At each step, try placing any letter that still has remaining tiles. Count each placement as one sequence, then recurse.

Algorithm

1. Count frequencies of each character.
2. Recursively try each character with remaining count > 0:
   • Decrement the count.
   • Add 1 for the current sequence.
   • Add the recursive count for extensions.
   • Restore the count.

Correctness

Since we iterate only over distinct characters at each step, duplicate sequences are avoided automatically. Every sequence corresponds to a unique path in the recursion tree.

Edge Cases

• Duplicates usually matter; store counts when a set would lose necessary multiplicity.
• Update the frequency structure in the same order the invariant assumes.
• Check empty or one-element inputs if the problem allows them.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

from collections import Counter

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        freq = Counter(tiles)

        def backtrack():
            count = 0
            for ch in freq:
                if freq[ch] > 0:
                    freq[ch] -= 1
                    count += 1 + backtrack()
                    freq[ch] += 1
            return count

        return backtrack()

Testing

def run_tests():
    s = Solution()

    assert s.numTilePossibilities("AAB") == 8
    assert s.numTilePossibilities("AAABBC") == 188
    assert s.numTilePossibilities("V") == 1

    print("all tests passed")

run_tests()