Stickers to Spell Word
Hard · Backtracking · Array · Hash Table · String · Dynamic Programming · Backtracking · Bitmask
Problem
You are given n kinds of stickers, each showing a lowercase English word in stickers, and you have an unlimited supply of every kind. You want to spell the string target by cutting individual letters out of stickers and rearranging them.
Return the minimum number of stickers needed to spell target, or -1 if it cannot be done. Letters left over on a sticker are simply wasted.
Examples
Input: stickers = ["ab","bc"], target = "abbc" Output: 2
One "ab" and one "bc" supply exactly a, b, b and c.
Input: stickers = ["aab","c"], target = "aaaac" Output: 3
Two "aab" stickers give four a's, and one "c" completes the word.
Input: stickers = ["xy"], target = "z" Output: -1
No sticker contains the letter z.
Constraints
- n == len(stickers)
- 1 <= n <= 50
- 1 <= len(stickers[i]) <= 10
- 1 <= len(target) <= 15
- stickers[i] and target consist of lowercase English letters
Approaches
- DP over bitmasks of target positions — time O(2^L · n · w · L), space O(2^L)
Follow-up
Why only stickers with the first needed letter? Every solution uses some sticker that supplies that letter. Applying that sticker first gives the same total, so restricting the first choice loses nothing and cuts the branching sharply. The use cases limit you to one copy of each sticker, and cover a set of skills with the fewest people.
Related problems
Start free on Cariara · Coding problems · System design studio
