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.#691 Stickers to Spell Word is a classic hard problem that combines dynamic programming, backtracking, and bitmasking. The goal is to determine the minimum number of stickers required to form a target string, where each sticker can contribute characters multiple times but each character can only be used once per sticker.
A common strategy is to preprocess each sticker into a frequency array of characters. Then use memoized recursion or DP to represent the remaining characters needed to build the target. At each step, try applying a sticker to reduce the remaining requirement and recursively compute the minimum number of stickers needed.
Another efficient perspective uses a bitmask to represent which positions of the target string have been formed. This converts the problem into exploring state transitions where applying a sticker fills additional positions in the mask. Memoization or DP ensures each state is solved once.
Because the state space depends on the target length, the time complexity is roughly O(m * 2^n * 26) where m is the number of stickers and n is the target length. Space complexity is mainly driven by the DP or memoization table.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DP with Bitmask on Target States | O(m * 2^n * 26) | O(2^n) |
| Memoized Backtracking with Character Counts | O(m * n * 2^n) (approx.) | O(2^n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
We want to perform an exhaustive search, but we need to speed it up based on the input data being random. For all stickers, we can ignore any letters that are not in the target word. When our candidate answer won't be smaller than an answer we have already found, we can stop searching this path. When a sticker dominates another, we shouldn't include the dominated sticker in our sticker collection. [Here, we say a sticker `A` dominates `B` if `A.count(letter) >= B.count(letter)` for all letters.]
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:
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.
1from collections import defaultdict
2import sys
3
4def minStickers(stickers, target):
5 n = len(stickers)
6 # Preprocess stickers into a list of letter-count dictionaries
7 sticker_count = [defaultdict(int) for _ in range(n)]
8 for i in range(n):
9 for char in stickers[i]:
10 sticker_count[i][char] += 1
11 memo = {}
12
13 def dfs(target):
14 if target in memo:
15 return memo[target]
16
17 target_count = defaultdict(int)
18 for char in target:
19 target_count[char] += 1
20
21 ans = sys.maxsize
22 # Try each sticker
23 for i in range(n):
24 if sticker_count[i][target[0]] == 0: # Cannot contribute to current first char
25 continue
26 # Construct a new target string after using this sticker
27 new_target = ''
28 for char in target_count:
29 if char in target_count:
30 needed = target_count[char] - sticker_count[i].get(char, 0)
31 if needed > 0:
32 new_target += char * needed
33
34 # Use one current sticker
35 if new_target != target: # If we made any progress
36 ans = min(ans, dfs(new_target) + 1)
37
38 memo[target] = ans if ans != sys.maxsize else -1
39 return memo[target]
40
41 result = dfs(target)
42 return result
43
44# Example Usage
45stickers = ["with", "example", "science"]
46target = "thehat"
47print(minStickers(stickers, target)) # Output: 3This 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.
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.
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.
1import java.util.*;
2
3
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.
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.
1from collections import Counter
2
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.
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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
public int MinStickers(string[] stickers, string target) {
int targetLength = target.Length;
int[] dp = new int[1 << targetLength];
Array.Fill(dp, int.MaxValue);
dp[0] = 0;
foreach (string sticker in stickers) {
var charCount = new int[26];
foreach (char c in sticker) charCount[c - 'a']++;
for (int state = 0; state < dp.Length; state++) {
if (dp[state] == int.MaxValue) continue;
int new_state = state;
var targetCharCount = new int[26];
for (int i = 0; i < targetLength; i++) {
if ((state & (1 << i)) == 0) targetCharCount[target[i] - 'a']++;
}
for (int i = 0; i < targetLength; i++) {
if ((state & (1 << i)) == 0 && charCount[target[i] - 'a'] > targetCharCount[target[i] - 'a']) {
new_state |= (1 << i);
}
}
dp[new_state] = Math.Min(dp[new_state], dp[state] + 1);
}
}
return dp[(1 << targetLength) - 1] == int.MaxValue ? -1 : dp[(1 << targetLength) - 1];
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem have appeared in interviews at large tech companies. It tests advanced problem-solving skills including dynamic programming, state compression, and optimization strategies.
Character frequency arrays and hash maps are commonly used to represent stickers and remaining characters efficiently. In bitmask-based solutions, integers represent states of the target string, enabling fast transitions and memoization.
The optimal approach uses dynamic programming with memoization or bitmasking to represent the state of the target string. Each state represents which characters are already formed, and stickers are applied to transition between states. This avoids recomputation and significantly reduces the search space.
The difficulty comes from the exponential state space and the need to combine multiple techniques like dynamic programming, backtracking, and pruning. Efficiently representing states and avoiding redundant computations is the key challenge.
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.
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.
This C# version uses dynamic programming with a bitmask technique similar to the C++ solution. It involves checking each combination of states and calculating the minimum stickers required for fulfilling each state in a manner that leverage sticker capacity to complete character requirements in the target word.