Letter Tile Possibilities: Counting with Backtracking

LeetCode 1079: Letter Tile Possibilities gives you a string tiles where each character represents a letter printed on a tile. You need to return the number of possible non-empty sequences of letters you can make using those tiles. Each tile can be used at most once per sequence, and two sequences are different if they differ in length or in at least one character at some position.

For example, given tiles = "AAB", the answer is 8: the valid sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", and "BAA".

tiles =freq: A=2, B=1

Why this problem matters

This is a permutations-with-duplicates problem in disguise, but with a twist: you need to count sequences of every possible length, not just full-length permutations. A naive approach would generate all possible arrangements, throw them into a set to deduplicate, and count the result. That works for small inputs but is wasteful. You end up generating the same sequence multiple times only to discard duplicates later.

The frequency-based backtracking approach is more elegant. Instead of tracking which index is used (and then deduplicating), you track how many of each character remain. You iterate over distinct characters, not positions. This means you never generate the same sequence twice in the first place. No set, no post-processing, no wasted work.

This pattern shows up in several related problems: Permutations II (generating unique full-length permutations), Subsets II (unique subsets from duplicates), and anywhere else you need to enumerate combinations from a multiset. Once you internalize the frequency-counting technique, all of these become variations of the same template.

The key insight

Use a character frequency map instead of tracking used indices. At each level of the recursion, iterate over distinct characters with a remaining count greater than zero. For each one, decrement its count, recurse, then restore it. Every single recursive call represents one valid sequence, so you add 1 to the count at every recursive call, not just at leaf nodes.

This is the part that trips people up. In problems like Permutations, you only record results when the sequence reaches full length. Here, partial sequences are valid too. The sequence "A" is just as valid as "AAB". So you count at every level of recursion: entering the function after choosing a character means you have formed a new non-empty sequence.

The solution

from collections import Counter

def num_tile_possibilities(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()

The outer function builds a frequency map from the input. For "AAB", this gives {A: 2, B: 1}.

Inside backtrack, we iterate over every key in the frequency map. If a character still has a count greater than zero, we decrement it (choose), then do count += 1 + backtrack(). The 1 accounts for the current sequence (the one formed by all characters chosen so far). The backtrack() call counts all longer sequences that extend from this point. After the recursive call returns, we increment the count back (unchoose).

The recursion naturally stops when no character has a count greater than zero. In that case, the loop body never executes and the function returns 0.

Notice there is no explicit "path" or "current sequence" parameter. We do not need to build the actual sequences, only count them. The frequency map itself is the only state, and we mutate-and-restore it across recursive calls.

Visual walkthrough

Let's trace through tiles = "AAB" step by step. Watch how the frequency map changes at each recursive call, and how every call adds exactly 1 to the total count.

The backtracking explores the entire tree without ever generating a duplicate sequence. The frequency map ensures that at each level, we only consider distinct characters. Since we have two A tiles but iterate over A once (decrementing its count), we never produce two identical branches at the same level.

Complexity analysis

Time: In the worst case (all unique characters), the recursion tree has n choices at the first level, n-1 at the second, and so on. This gives O(n!) nodes. With duplicates, the tree is smaller because characters with the same letter share a single branch at each level. The sum n + n*(n-1) + n*(n-1)*(n-2) + ... is bounded by e * n! (roughly 2.718 * n!), so the time complexity is O(n!).

Space: The recursion depth is at most n (one level per tile). The frequency map uses O(k) space where k is the number of distinct characters, and k is at most n. So total space is O(n) for the call stack plus O(k) for the map, which simplifies to O(n).

The building blocks

1. Frequency-based choice pattern

Instead of iterating over array indices and skipping used ones, you iterate over a frequency map. This is the cleanest way to handle duplicate elements in backtracking:

for ch in freq:
    if freq[ch] > 0:
        freq[ch] -= 1
        explore(ch)
        freq[ch] += 1

Each character appears in the loop exactly once, regardless of how many copies exist. The count controls how many times it can be chosen across different levels. This pattern eliminates duplicates structurally rather than by checking after the fact.

2. Count at every level of recursion

In standard permutation problems, you record results only at the base case (full-length permutations). Letter Tile Possibilities requires counting at every level because partial sequences are valid. The pattern is:

def backtrack():
    count = 0
    for choice in available:
        count += 1
        count += backtrack()
    return count

Every entry into the loop body means a new character was chosen, forming a new valid sequence. The recursive call then counts all longer extensions. This "count at every level" pattern applies whenever the problem asks for all non-empty subsequences or partial arrangements, not just complete ones.

Edge cases

• Single tile: tiles = "A" returns 1. Only one possible sequence.
• All identical tiles: tiles = "AAA" returns 3. The sequences are "A", "AA", "AAA". Even though there are three tiles, the frequency approach only branches on A once per level.
• All distinct tiles: tiles = "ABCDEFG" (7 unique letters). This is the worst case for runtime. The answer equals the sum of P(7,1) + P(7,2) + ... + P(7,7) = 13699.
• Empty result check: The constraints guarantee at least 1 tile, so you never return 0. But the function handles it naturally since the loop would not execute with an empty map.
• Maximum input: tiles can be up to length 7, so even the worst case (7! nodes) is fast. The constraint is small enough that the backtracking approach runs in microseconds.

From understanding to recall

You see how the frequency map eliminates duplicates and how counting at every recursive call captures partial sequences. The algorithm is compact: a frequency map, a loop over distinct characters, decrement-recurse-restore, and count += 1 + backtrack(). But can you write it from scratch in under two minutes?

That is the gap between understanding and interview readiness. Under pressure, people forget to count at every level (only counting at leaves), or they try to track indices and get tangled in duplicate-skipping logic. The frequency-based approach is cleaner, but it needs to be automatic. Spaced repetition drills the pattern until it is second nature. You see "tile possibilities" or "count unique sequences with duplicates" and the frequency-backtracking template comes out without hesitation.

Related posts

• Permutations II - Generating all unique permutations with duplicates
• Subsets II - Generating unique subsets with duplicate elements
• Letter Combinations of a Phone Number - Another backtracking letter generation problem

CodeBricks breaks Letter Tile Possibilities into its frequency-backtracking building block, then drills it independently with spaced repetition. You type the backtracking function from scratch until it is automatic. When a backtracking problem with duplicates shows up in your interview, you do not think about it. You just write it.