> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Stickers to Spell Word Python Solution

> Tested Python solution for LeetCode 691 with 13 pytest cases. Generate a practice environment with lcpy.

LeetCode 691, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [String](/catalog/topics/string), [Dynamic Programming](/catalog/topics/dynamic-programming), [Backtracking](/catalog/topics/backtracking), [Bit Manipulation](/catalog/topics/bit-manipulation), [Bitmask](/catalog/topics/bitmask). [View on LeetCode](https://leetcode.com/problems/stickers-to-spell-word/description/).

Generate this problem as a practice environment: tested reference solution, 13 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 691   # by problem number
lcpy gen -s stickers_to_spell_word   # by problem name
```

## Problem

We are given `n` different types of stickers. Each sticker has a lowercase English word on it.

You would like to spell out the given string `target` by cutting individual letters from your collection of stickers and rearranging them. You can use each sticker more than once if you want, and you have infinite quantities of each sticker.

Return the minimum number of stickers that you need to spell out `target`. If the task is impossible, return `-1`.

Note: In all test cases, all words were chosen randomly from the 1000 most common US English words, and target was chosen as a concatenation of two random words.

### Examples

```
Input: stickers = ["with","example","science"], target = "thehat"
Output: 3
Explanation: We can use 2 "with" stickers, and 1 "example" sticker.
After cutting and rearrange the letters of those stickers, we can form the target "thehat".
Also, this is the minimum number of stickers necessary to form the target string.
```

```
Input: stickers = ["notice","possible"], target = "basicbasic"
Output: -1
Explanation: We cannot form the target "basicbasic" from cutting letters from the given stickers.
```

### Constraints

* n == stickers.length
* 1 \<= n \<= 50
* 1 \<= stickers\[i].length \<= 10
* 1 \<= target.length \<= 15
* stickers\[i] and target consist of lowercase English letters.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/stickers_to_spell_word/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/stickers_to_spell_word/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from functools import cache


class Solution:
    # Time: O(2^m * n * m) where m = len(target), n = len(stickers)
    # Space: O(2^m)
    def min_stickers(self, stickers: list[str], target: str) -> int:
        m = len(target)
        full = (1 << m) - 1
        sticker_counts: list[list[int]] = []
        for sticker in stickers:
            counts = [0] * 26
            for ch in sticker:
                counts[ord(ch) - ord("a")] += 1
            sticker_counts.append(counts)

        @cache
        def dp(mask: int) -> int:
            if mask == full:
                return 0
            # A usable sticker covers at least one letter, so m is an upper bound
            best = m + 1
            for counts in sticker_counts:
                remaining = counts[:]
                new_mask = mask
                for i in range(m):
                    pos = ord(target[i]) - ord("a")
                    if not mask >> i & 1 and remaining[pos]:
                        remaining[pos] -= 1
                        new_mask |= 1 << i
                if new_mask != mask:
                    best = min(best, 1 + dp(new_mask))
            return best

        result = dp(0)
        return result if result <= m else -1
```

## Complexity

| Time | Space |
| - | - |
| O(2^m \* n \* m) where m = len(target), n = len(stickers) | O(2^m) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.