#691

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Stickers to Spell Word

Determine the minimum number of stickers needed to spell a target word using array scanning and hash lookups for efficient letter tracking.

array hash table string dynamic programming backtracking

Problem Statement

You are given a collection of n stickers, each containing a lowercase English word. Your goal is to spell out a given target string by cutting letters from these stickers and rearranging them. Stickers can be used multiple times, and each letter can be used only as many times as it appears in the sticker.

Return the minimum number of stickers needed to spell the target. If it is impossible to form the target from the available stickers, return -1. Constraints: 1 <= n <= 50, 1 <= sticker length <= 10, 1 <= target length <= 15.

Examples

Example 1

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

Output: 3

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.

Example 2

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

Output: -1

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 Approach

Convert Stickers to Letter Frequency Maps

Scan each sticker and create a hash map of letter counts. This lets you quickly determine how many times each sticker can contribute to forming letters in the target, a core part of the array scanning plus hash lookup pattern.

Recursive Search with Memoization

Recursively attempt to build the target by subtracting letters covered by chosen stickers, storing intermediate results in a memoization table. This prevents redundant calculations and efficiently handles the combinatorial explosion of sticker selections.

Prune Irrelevant Stickers Early

For each recursion, skip stickers that do not contribute new letters to the remaining target. This leverages the input's sparsity and avoids unnecessary branches, a common failure mode when the search space grows too large.

Complexity Analysis

Metric	Value
Time	O(2^T * S * T)
Space	O(2^T)

Time complexity is O(2^T * S * T), where T is the target length and S is the number of stickers, due to the recursive exploration of all target subsets with each sticker. Space complexity is O(2^T) for memoization storing subsets of the target.

What Interviewers Usually Probe

Look for solutions using array scanning combined with hash maps to track letter frequencies.
Expect candidates to discuss memoization to avoid repeated calculations in the combinatorial search.
Watch for pruning strategies that reduce unnecessary recursive calls when stickers contribute no new letters.

Common Pitfalls or Variants

Common pitfalls

Failing to memoize results, causing exponential time due to redundant recursive calls.
Attempting to use each sticker only once rather than allowing multiple uses.
Not pruning stickers that do not contribute to the remaining target, leading to wasted computation.

Follow-up variants

Limiting the number of times each sticker can be used, requiring more careful counting.
Target words with repeated letters appearing more than any single sticker can provide, testing aggregation logic.
Stickers with overlapping letters where multiple sticker combinations yield the same target letters, challenging pruning strategies.

FAQ

What is the main pattern used in Stickers to Spell Word?

The core pattern is array scanning plus hash lookup, using frequency maps of stickers to track letters and recursively cover the target.

Can each sticker be used multiple times?

Yes, each sticker can be reused infinitely, but you must account for its letter counts when forming the target.

Why is memoization important for this problem?

Memoization avoids recalculating the minimum stickers for the same remaining target, drastically reducing recursive calls and runtime.

What should I do if a target cannot be formed?

Return -1 immediately if no sticker combination can cover all letters of the target, as indicated by the recursive exploration.

How does pruning irrelevant stickers improve performance?

Skipping stickers that add no new letters prevents unnecessary recursive branches, reducing the combinatorial explosion inherent in exhaustive search.

terminal

Solution

Solution 1: BFS + State Compression

We notice that the length of the string `target` does not exceed 15. We can use a binary number of length 15 to represent whether each character of `target` has been spelled out. If the $i$th bit is 1, it means that the $i$th character of `target` has been spelled out; otherwise, it has not been spelled out.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        n = len(target)
        q = deque([0])
        vis = [False] * (1 << n)
        vis[0] = True
        ans = 0
        while q:
            for _ in range(len(q)):
                cur = q.popleft()
                if cur == (1 << n) - 1:
                    return ans
                for s in stickers:
                    cnt = Counter(s)
                    nxt = cur
                    for i, c in enumerate(target):
                        if (cur >> i & 1) == 0 and cnt[c] > 0:
                            cnt[c] -= 1
                            nxt |= 1 << i
                    if not vis[nxt]:
                        vis[nxt] = True
                        q.append(nxt)
            ans += 1
        return -1

Continue Practicing

#698 partition to k equal sum subsets #638 shopping offers #996 number of squareful arrays