Stickers to Spell Word: BFS on Letter States

LeetCode 691 "Stickers to Spell Word" gives you a set of stickers, each printed with a lowercase English word. You can cut individual letters from any sticker and rearrange them to spell a target string. Each sticker can be used as many times as you want. Your goal is to find the minimum number of stickers needed to spell the target, or return -1 if it is impossible.

The approach: BFS on remaining-letter states

The key insight is that the order you apply stickers does not matter. What matters is the set of letters still needed at each point. You can represent the current "state" as the sorted string of remaining letters. BFS from the full target toward the empty string gives you the shortest path, which corresponds to the fewest stickers.

At each BFS level, you try applying every sticker to the current remaining-letter state. Applying a sticker means removing the letters it provides (using frequency counts). After applying a sticker, sort the leftover letters to create a canonical state string. If you reach the empty string, the current BFS depth is your answer.

The critical pruning trick: for each state, only try stickers that contain the first remaining letter. Since you will eventually need a sticker for that letter anyway, restricting your choices to stickers containing it avoids exploring redundant orderings (where you would reach the same state via a different sticker order).

from collections import Counter

def minStickers(stickers: list[str], target: str) -> int:
    sticker_counts = [Counter(s) for s in stickers]
    queue = [target]
    visited = {"": 0}
    visited[target] = 0
    steps = 0
    while queue:
        steps += 1
        next_queue = []
        for remain in queue:
            for sc in sticker_counts:
                if remain[0] not in sc:
                    continue
                left = list(remain)
                for ch, cnt in sc.items():
                    for _ in range(cnt):
                        if ch in left:
                            left.remove(ch)
                new_remain = "".join(sorted(left))
                if not new_remain:
                    return steps
                if new_remain not in visited:
                    visited[new_remain] = steps
                    next_queue.append(new_remain)
        queue = next_queue
    return -1

Step-by-step walkthrough

Complexity analysis

Where t = length of target, n = number of stickers.

The number of distinct remaining-letter states is bounded by 2^t in theory, since each letter in the target is either still needed or already covered. In practice, sorting the remaining letters to canonicalize the state and the first-letter pruning strategy keep the actual state space much smaller. Each state may be processed with up to n stickers, and applying a sticker costs O(t) to subtract letters. The space is dominated by the visited set, which holds at most 2^t canonical state strings.

The building blocks

BFS on abstract states

Instead of running BFS on a graph of nodes and edges, you run BFS on an abstract state space where each "node" is a string of remaining letters. The transitions are sticker applications. This is the same pattern you see in word ladder problems, where each word is a node and edges connect words that differ by one letter. The generalization is powerful: any time you need a minimum number of steps to transform one configuration into another, BFS on the state space works.

Frequency counting for set subtraction

When you apply a sticker, you need to remove the letters it provides from the remaining letters. Using Counter (or a frequency map) makes this efficient. For each character in the sticker's frequency map, you remove up to that many copies from the remaining list. This avoids the quadratic cost of scanning and removing one letter at a time from a naive approach.

First-letter pruning

At any state, you know the first remaining letter must be covered by some sticker eventually. By only trying stickers that contain that letter, you avoid exploring paths where you apply unrelated stickers first and then circle back. This does not miss any optimal solutions because any valid sequence can be reordered so that the sticker covering the first remaining letter comes first.

Edge cases

• Target already empty: If the target string is empty, the answer is 0 since no stickers are needed.
• Impossible to spell: If some letter in the target does not appear in any sticker, return -1 immediately. You can check this before starting BFS.
• Single sticker suffices: If one sticker contains all the letters needed (accounting for frequencies), the answer is 1.
• Repeated letters in target: The target "aab" requires stickers that collectively provide at least two "a" letters and one "b". Frequency counting handles this naturally.
• Redundant stickers: If sticker A's letter set is a subset of sticker B's letter set, you can safely ignore sticker A. This is an optional optimization that reduces the branching factor.

From understanding to recall

This problem combines BFS level-by-level exploration with frequency-based set subtraction and a clever pruning rule. To internalize it, practice writing the BFS loop from scratch, paying attention to three things: how you represent states (sorted remaining letters), how you apply a sticker (subtract its letter counts), and how you prune (only try stickers matching the first letter). Revisiting this problem at increasing intervals will help you recognize the "minimum operations on a shrinking set" pattern in other problems.

Related posts

• Word Break - Another problem about composing a target from pieces, solved with DP/BFS on remaining substrings
• Coin Change - BFS for minimum count where items can be reused, the same "fewest items to reach a target" structure
• Combination Sum - Exploring combinations with unlimited reuse, similar to trying each sticker at each step