LeetCode 691: Stickers to Spell Word

Problem Restatement

We are given a list of sticker words and a target string.

Each sticker contains lowercase English letters. We may cut letters from stickers and rearrange them to form the target.

We have infinite copies of every sticker, so the same sticker type can be used more than once.

Return the minimum number of stickers needed to form target.

If it is impossible, return -1. The official statement says each sticker may be used more than once and each sticker supplies individual letters that can be rearranged.

Input and Output

Example function shape:

def minStickers(stickers: list[str], target: str) -> int:
    ...

Examples

Example 1:

stickers = ["with", "example", "science"]
target = "thehat"

One optimal way is to use:

"with" + "example" + "with"

These stickers can provide the letters needed for "thehat".

Answer:

3

Example 2:

stickers = ["notice", "possible"]
target = "basicbasic"

The target needs letters such as 'a' and 'b'.

The stickers do not provide enough useful letters to form the target.

Answer:

-1

First Thought: Try Every Sticker Combination

A direct approach is to try all possible choices of stickers.

At each step, choose one sticker, subtract its letters from the remaining target, and recurse.

This can find the answer, but the search tree can be very large because:

We need memoization so the same remaining target is solved only once.

Key Insight

The important state is not the exact sequence of stickers used so far.

The important state is:

Which letters are still needed?

For example, if the current remaining target is:

"thehat"

and we use sticker:

"with"

then "with" can cover one 't' and one 'h'.

The remaining letters are:

"aeht"

Now the problem becomes:

How many more stickers are needed to form "aeht"?

This gives a recursive dynamic programming structure.

State Representation

We store the remaining target as a sorted string.

For example:

"thehat"

has counts:

A remaining state can be represented as:

"aehhtt"

Sorting gives a canonical representation, so equivalent remaining-letter multisets share the same memo key.

Algorithm

First, preprocess each sticker into a frequency array of size 26.

Then define:

dp(remaining)

as the minimum number of stickers needed to form the string remaining.

Base case:

dp("") = 0

For a non-empty remaining:

1. Count the letters needed in remaining.
2. Try each sticker.
3. Skip stickers that do not contain the first character of remaining.
4. Subtract the sticker’s letters from the needed counts.
5. Build the next remaining string.
6. Recursively solve it.
7. Take the minimum over all stickers:

   1 + dp(next_remaining)

The skip rule is an optimization.

If a sticker does not contain the first needed character, using it now cannot be part of an optimal first step for this canonical state, because we can choose a useful sticker first instead.

Walkthrough

Consider:

stickers = ["with", "example", "science"]
target = "thehat"

Start:

remaining = "aehhtt"

Try sticker "with".

It provides:

The target needs:

After using "with", remaining letters are:

"aeht"

Then we solve:

dp("aeht")

Trying more stickers eventually finds that 3 stickers are enough.

Correctness

Let dp(remaining) be the minimum number of stickers needed to form exactly the multiset of letters in remaining.

If remaining is empty, no stickers are needed, so dp("") = 0.

For a non-empty remaining, any valid solution must choose some first sticker. After using that sticker, some letters from remaining are covered, and the uncovered letters form a smaller remaining state.

The total number of stickers for that choice is:

1 + dp(next_remaining)

The algorithm tries every useful sticker as this first sticker, computes the resulting remaining state, and takes the minimum.

By memoization, each remaining state is solved once, and recursive calls use the same definition of optimality.

If no sticker can reduce the remaining target, the state is impossible.

Therefore, dp(target) gives the minimum number of stickers needed to form the target, or reports impossibility.

Complexity

Let:

Since target.length <= 15, the number of distinct remaining states is bounded by a function of 2^t in bitmask formulations, or by the number of reachable multisets in the count-string formulation.

A common bitmask DP analysis is O(2^t * m * L * t) time and O(2^t) space.

Implementation

from collections import Counter
from functools import lru_cache

class Solution:
    def minStickers(self, stickers: list[str], target: str) -> int:
        sticker_counts = []

        for sticker in stickers:
            sticker_counts.append(Counter(sticker))

        @lru_cache(None)
        def dp(remaining: str) -> int:
            if not remaining:
                return 0

            need = Counter(remaining)
            first_char = remaining[0]
            best = float("inf")

            for sticker in sticker_counts:
                if sticker[first_char] == 0:
                    continue

                next_remaining = []

                for ch, count in need.items():
                    leftover = count - sticker[ch]

                    if leftover > 0:
                        next_remaining.append(ch * leftover)

                next_state = "".join(sorted(next_remaining))
                sub_answer = dp(next_state)

                if sub_answer != -1:
                    best = min(best, 1 + sub_answer)

            return -1 if best == float("inf") else best

        return dp("".join(sorted(target)))

Code Explanation

We first convert each sticker into a character counter:

sticker_counts.append(Counter(sticker))

This lets us quickly know how many copies of each letter a sticker provides.

The memoized function:

def dp(remaining: str) -> int:

returns the minimum number of stickers needed to form remaining.

The empty string needs no stickers:

if not remaining:
    return 0

We count the letters still needed:

need = Counter(remaining)

Then we try every sticker.

This optimization skips stickers that cannot cover the first remaining character:

if sticker[first_char] == 0:
    continue

For each useful sticker, we subtract its letters from need.

Only positive leftovers are kept:

leftover = count - sticker[ch]

if leftover > 0:
    next_remaining.append(ch * leftover)

Then we create the next canonical state:

next_state = "".join(sorted(next_remaining))

If the recursive result is possible, we update the best answer:

best = min(best, 1 + sub_answer)

Finally, if no sticker works, return -1.

Testing

def run_tests():
    s = Solution()

    assert s.minStickers(
        ["with", "example", "science"],
        "thehat",
    ) == 3

    assert s.minStickers(
        ["notice", "possible"],
        "basicbasic",
    ) == -1

    assert s.minStickers(
        ["these", "guess", "about", "garden", "him"],
        "atomher",
    ) == 3

    assert s.minStickers(
        ["a", "b", "ab"],
        "abab",
    ) == 2

    assert s.minStickers(
        ["abc"],
        "abcabc",
    ) == 2

    print("all tests passed")

run_tests()

Test meaning: