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.
This approach utilizes recursive backtracking in combination with memoization to solve the problem. The idea is to maintain a count of letters that are still needed to complete the target string and recursively explore combinations of stickers that reduce this count. Memoization helps in caching previously computed results for specific target states, avoiding redundant calculations.
The steps are as follows:
This Python solution utilizes a recursive function with memoization to determine the minimum number of stickers needed. It preprocesses each sticker to count letter frequencies and applies DFS to explore useful sticker combinations. Memoization caches results for recurring target patterns, efficiently solving overlapping subproblems.
Python
Time Complexity: O(T * 2^T * S), where T is the length of the target, and S is the number of stickers. This accounts for checking each subset of the target matched with each sticker.
Space Complexity: O(T * k), where k is the average word length in stickers, for the memoization storage.
In this approach, a depth-first search (DFS) strategy is employed, utilizing bitmasking to represent the state of the target string. Each bit corresponds to a character position in the target, and a bit set to 1 indicates that a letter is needed. This makes it efficient to track state transitions and reuse computed outcomes using a bitmask.
The bitmask representation simplifies target state management, especially with small problems like this one where all state combinations fit comfortably in integer bit representation.
The solution implemented in Java leverages bitmasking along with a memoization HashMap to efficiently calculate the minimum number of stickers required. The helper function explores possible sticker applications iteratively, adjusting the target state and caching results to avoid redundant calculations.
Java
Time Complexity: O(2^T * n * T), where T is the target length and n the number of stickers, reflecting operations per state per sticker.
Space Complexity: O(2^T + n), for the dp table managing the state combinations and sticker reading.
A Depth First Search (DFS) approach combined with memoization can efficiently solve this problem. By recursively exploring each possible configuration of using stickers to form the target and caching results for already computed subproblems, we minimize redundant calculations.
The idea is to count the frequency of each character needed for the target and use it to explore different combinations of stickers. We process stickers in such a way that each branch of our recursive call attempts to use the result of one sticker to reduce the requirement for the remaining target. Memoization is used to store results for target states we've already calculated for.
This Python solution utilizes DFS with memoization to navigate possible sticker usage combinations recursively. The Counter from the collections module is used to manage and compare character frequencies efficiently. A nested function dfs() handles the recursions, checking if a given state of the target string has been computed before or if it can be completed with the current stickers. If a target can be formed, it records the minimum number of stickers required.
Time Complexity: O(2^T * N * L), where T is the length of the target, N is the number of stickers, and L is the average length of a sticker.
Space Complexity: O(T), for the memoization cache.
This approach uses dynamic programming with bit masking to keep track of which characters in the target have been fulfilled. The idea is to use a bit mask to represent the completeness of parts of the target. Each bit in the mask represents whether a character in the target has been used or not.
By iterating over each sticker, we apply the possible contribution of each sticker to partially fulfill the target (indicated by updating the bitmask). A DP array helps record the minimum sticker usage to reach any given bitmap state of the target.
This C++ solution employs a dynamic programming approach with bitmasking. The DP array keeps track of the minimum number of stickers required to attain various states of completeness of the target string, which are represented via bit masks. Each state explores how stickers can contribute to completing the target, and bit masking efficiently labels which parts are completed or pending.
Time Complexity: O(N * T * 2^T), where T is the length of the target, N is the number of stickers.
Space Complexity: O(2^T), for the DP array.
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 ith bit is 1, it means that the ith character of target has been spelled out; otherwise, it has not been spelled out.
We define an initial state 0, which means that all characters have not been spelled out. Then we use the Breadth-First Search (BFS) method, starting from the initial state. Each time we search, we enumerate all the stickers. For each sticker, we try to spell out each character of target. If we spell out a character, we set the ith bit of the corresponding binary number to 1, indicating that the character has been spelled out. Then we continue to search until we spell out all the characters of target.
The time complexity is O(2^n times m times (l + n)), and the space complexity is O(2^n). Where n is the length of the string target, and m and l are the number of stickers and the average length of the stickers, respectively.
| Approach | Complexity |
|---|---|
| Recursive Backtracking with Memoization | Time Complexity: O(T * 2^T * S), where T is the length of the target, and S is the number of stickers. This accounts for checking each subset of the target matched with each sticker. Space Complexity: O(T * k), where k is the average word length in stickers, for the memoization storage. |
| DFS and Bitmasking Optimization | Time Complexity: O(2^T * n * T), where T is the target length and n the number of stickers, reflecting operations per state per sticker. Space Complexity: O(2^T + n), for the dp table managing the state combinations and sticker reading. |
| DFS with Memoization | Time Complexity: O(2^T * N * L), where T is the length of the target, N is the number of stickers, and L is the average length of a sticker. |
| Bit-Masked Dynamic Programming | Time Complexity: O(N * T * 2^T), where T is the length of the target, N is the number of stickers. |
| BFS + State Compression | — |
| 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 |
Stickers to Spell Word - DP Memoization - Leetcode 691 - Python • NeetCode • 30,865 views views
Watch 9 more video solutions →Practice Stickers to Spell Word with our built-in code editor and test cases.
Practice on FleetCode