Watch 10 video solutions for Stickers to Spell Word, a hard level problem involving Array, String, Dynamic Programming. This walkthrough by NeetCode has 30,865 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
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.
Example 2:
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.length1 <= n <= 501 <= stickers[i].length <= 101 <= target.length <= 15stickers[i] and target consist of lowercase English letters.Problem Overview: You are given several sticker strings and a target word. Each sticker can be used multiple times, and each character from a sticker can be used once per usage. The goal is to compute the minimum number of stickers required to assemble the target string.
Approach 1: Recursive Backtracking with Memoization (Time: O(n * 2^m * m), Space: O(2^m))
This approach treats the remaining characters of the target as the state. For each recursive step, you try applying every sticker and reduce the characters it can cover. The key optimization is memoization: cache the minimum number of stickers required for each remaining target configuration. Without caching, the recursion repeatedly solves identical subproblems. With memoization, each state is computed once, turning an exponential brute force into a manageable search over unique states.
Approach 2: DFS with Memoization (Frequency Optimization) (Time: O(n * m * states), Space: O(states))
Instead of repeatedly rebuilding strings, this version converts every sticker into a 26-length frequency array. During DFS, you compute the remaining target after applying a sticker by subtracting character counts. Memoization stores the best answer for each remaining string state. This reduces string manipulation overhead and speeds up pruning when a sticker contributes no useful characters. The technique combines backtracking with caching to avoid recomputation.
Approach 3: DFS with Bitmasking Optimization (Time: O(n * 2^m * m), Space: O(2^m))
When the target length is small (usually ≤15), you can represent which characters are already formed using a bitmask. Each bit represents whether that position in the target is covered. DFS tries to apply each sticker and sets additional bits when matching characters are found. The state becomes a mask integer instead of a string, making memoization much faster. This approach leverages bitmask state compression to represent subsets of the target efficiently.
Approach 4: Bit-Masked Dynamic Programming (Time: O(n * 2^m * m), Space: O(2^m))
This bottom-up solution uses dynamic programming where dp[mask] represents the minimum stickers required to build the subset of target characters represented by mask. Starting from dp[0] = 0, iterate through all masks and try applying each sticker to transition into a new mask with additional characters filled. Since there are only 2^m possible states, the algorithm systematically computes the minimum stickers for every subset. This is a classic subset DP pattern from dynamic programming.
Recommended for interviews: DFS with memoization or bitmask DP are the most common interview solutions. Starting with recursive backtracking shows understanding of the search space, but adding memoization or bitmask state compression demonstrates strong optimization skills. Interviewers usually expect the O(n * 2^m) style solution because it efficiently handles the exponential combinations of target characters.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking with Memoization | O(n * 2^m * m) | O(2^m) | When starting with brute force and optimizing repeated states using caching |
| DFS with Memoization (Frequency Arrays) | O(n * m * states) | O(states) | General practical solution with reduced string manipulation overhead |
| DFS with Bitmasking | O(n * 2^m * m) | O(2^m) | When target length is small and bitmask state compression is feasible |
| Bit-Masked Dynamic Programming | O(n * 2^m * m) | O(2^m) | When you want a systematic bottom-up DP over all subsets |