# 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

| Item | Meaning |
|---|---|
| Input | `stickers`, a list of strings, and `target`, a string |
| Output | Minimum number of stickers needed, or `-1` |
| Sticker use | Unlimited copies |
| Letter use | Each letter from a chosen sticker can be used once |
| Rearrangement | Allowed |
| Constraint | `target.length <= 15` in the standard LeetCode constraints |

Example function shape:

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

## Examples

Example 1:

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

One optimal way is to use:

```text
"with" + "example" + "with"
```

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

Answer:

```python
3
```

Example 2:

```python
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:

```python
-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:

| Issue | Meaning |
|---|---|
| Stickers can be reused | The same sticker may appear many times |
| Order does not matter | Many different orders produce the same remaining target |
| States repeat | Different paths may leave the same remaining letters |

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:

```text
Which letters are still needed?
```

For example, if the current remaining target is:

```python
"thehat"
```

and we use sticker:

```python
"with"
```

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

The remaining letters are:

```python
"aeht"
```

Now the problem becomes:

```text
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:

```text
"thehat"
```

has counts:

| Letter | Count |
|---|---:|
| `a` | 1 |
| `e` | 1 |
| `h` | 2 |
| `t` | 2 |

A remaining state can be represented as:

```text
"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:

```python
dp(remaining)
```

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

Base case:

```python
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:
   ```text id="6v5q39"
   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:

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

Start:

```text
remaining = "aehhtt"
```

Try sticker `"with"`.

It provides:

| Letter | Count |
|---|---:|
| `w` | 1 |
| `i` | 1 |
| `t` | 1 |
| `h` | 1 |

The target needs:

| Letter | Count |
|---|---:|
| `a` | 1 |
| `e` | 1 |
| `h` | 2 |
| `t` | 2 |

After using `"with"`, remaining letters are:

```text
"aeht"
```

Then we solve:

```text
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:

```text
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:

| Symbol | Meaning |
|---|---|
| `m` | Number of stickers |
| `L` | Maximum sticker length |
| `t` | Length of `target` |

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.

| Metric | Value | Why |
|---|---:|---|
| Time | Exponential in `t`, with memoization | The problem is a small-state combinatorial DP |
| Space | Exponential in `t` | Memo table stores remaining-target states |

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

## Implementation

```python
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:

```python
sticker_counts.append(Counter(sticker))
```

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

The memoized function:

```python
def dp(remaining: str) -> int:
```

returns the minimum number of stickers needed to form `remaining`.

The empty string needs no stickers:

```python
if not remaining:
    return 0
```

We count the letters still needed:

```python
need = Counter(remaining)
```

Then we try every sticker.

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

```python
if sticker[first_char] == 0:
    continue
```

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

Only positive leftovers are kept:

```python
leftover = count - sticker[ch]

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

Then we create the next canonical state:

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

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

```python
best = min(best, 1 + sub_answer)
```

Finally, if no sticker works, return `-1`.

## Testing

```python
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:

| Test | Expected | Why |
|---|---:|---|
| `["with","example","science"]`, `"thehat"` | `3` | Official positive example |
| `["notice","possible"]`, `"basicbasic"` | `-1` | Official impossible example |
| Mixed stickers, `"atomher"` | `3` | Checks multiple useful sticker choices |
| `["a","b","ab"]`, `"abab"` | `2` | Best choice uses `"ab"` twice |
| `["abc"]`, `"abcabc"` | `2` | Same sticker can be reused |