691. Stickers to Spell Word
Problem Description
You have n
different types of stickers, where each sticker contains a lowercase English word. You need to spell out a given target
string by cutting individual letters from your stickers and rearranging them.
Key points:
- You can use each sticker multiple times (infinite supply of each sticker type)
- You can cut individual letters from any sticker and use them in any order
- The goal is to collect enough letters to spell the entire
target
string
Your task is to find the minimum number of stickers needed to spell out the target
. If it's impossible to spell the target using the available stickers, return -1
.
For example, if you have stickers with words ["with", "example", "science"]
and need to spell "thehat"
:
- You could use the sticker
"with"
to get letters 't' and 'h' - Use another
"with"
to get another 'h' - Use
"example"
to get 'e' and 'a' - Use
"with"
again to get the final 't' - This would require 4 stickers total (though this might not be the optimal solution)
The solution uses BFS with state compression, where each state is represented as a bitmask indicating which characters of the target
have been collected. Starting from state 0
(no characters collected), the algorithm explores all possible ways to add stickers, updating the state by setting bits corresponding to newly collected characters. The search continues level by level until reaching state (1 << n) - 1
(all characters collected), returning the number of levels traversed as the minimum stickers needed.
Flowchart Walkthrough
First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- No: While the solution uses BFS which is typically associated with graphs, the problem itself is not about traversing nodes and edges in a traditional graph structure. We're dealing with collecting letters from stickers to form a target string.
Need to solve for kth smallest/largest?
- No: We're looking for the minimum number of stickers needed, not the kth smallest/largest element.
Involves Linked Lists?
- No: The problem involves strings and stickers, not linked list data structures.
Does the problem have small constraints?
- Yes: The target string length is at most 15 characters (as mentioned in the solution approach). This small constraint allows us to use state compression with bitmasks, where we can represent all possible states with
2^15
combinations.
Brute force / Backtracking?
- Yes: With small constraints (target length ≤ 15), we can explore different combinations of stickers. The solution effectively uses a brute force approach with BFS, trying all possible sticker combinations and tracking which characters have been collected using state compression. While implemented as BFS, this is conceptually similar to backtracking - we're exploring all possible paths (sticker selections) to reach our goal state.
Conclusion: The flowchart correctly identifies this as a problem suitable for brute force/backtracking due to the small constraints. The actual implementation uses BFS with state compression as an optimized way to explore all possible combinations of stickers, which is essentially a systematic brute force search through the solution space.
Intuition
When we first look at this problem, we need to find the minimum number of stickers to spell out a target string. This immediately suggests we need to explore different combinations of stickers and find the optimal one.
The key insight is recognizing that the target string has a maximum length of 15 characters. This small constraint is crucial - it means we can track which characters we've collected using a bitmask. Each bit position represents whether we've collected the character at that position in the target string.
Why BFS instead of traditional backtracking? Think about the problem structure:
- We want the minimum number of stickers (shortest path)
- Each "step" involves using one sticker
- We can represent our progress as states (which characters we've collected so far)
This naturally fits a BFS pattern where we explore all possible states level by level. Each level represents using one additional sticker. The first time we reach the complete state (all characters collected), we've found the minimum number of stickers needed.
The state compression technique comes from observing that:
- We only care about which characters we've collected, not the order
- With 15 characters max, we have at most
2^15 = 32,768
possible states - We can represent each state as an integer where bit
i
indicates if we've collected thei
-th character
For each state, we try adding each available sticker. When we use a sticker, we greedily take as many useful characters as possible from it (characters that we still need). This generates a new state with more bits set to 1.
The visited array prevents us from exploring the same state multiple times - once we've reached a particular combination of collected characters with k
stickers, there's no point reaching the same combination with more stickers.
Learn more about Memoization, Dynamic Programming, Backtracking and Bitmask patterns.
Solution Approach
The solution implements BFS with state compression to find the minimum number of stickers needed.
State Representation:
- We use a bitmask to represent which characters of the target have been collected
- If bit
i
is set to 1, it means the character at positioni
in the target has been collected - Initial state is
0
(no characters collected) - Goal state is
(1 << n) - 1
(all bits set, all characters collected)
BFS Implementation:
-
Initialize the queue with state
0
and mark it as visited -
Process level by level (each level represents using one more sticker):
for _ in range(len(q)): # Process all states at current level
-
For each state, try all stickers:
- Create a counter for the current sticker's characters:
cnt = Counter(s)
- Start with the current state:
nxt = cur
- Create a counter for the current sticker's characters:
-
Greedily collect characters from the sticker:
for i, c in enumerate(target): if (cur >> i & 1) == 0 and cnt[c] > 0: # Character not collected yet and available cnt[c] -= 1 # Use this character from sticker nxt |= 1 << i # Set bit i to 1 (mark as collected)
(cur >> i & 1) == 0
checks if biti
is 0 (character not collected)cnt[c] > 0
checks if the sticker has this character availablenxt |= 1 << i
sets biti
to 1 in the new state
-
Add new states to the queue:
- Only add unvisited states to avoid redundant exploration
- Mark the new state as visited
-
Check for completion:
- If we reach state
(1 << n) - 1
, all characters are collected - Return the current level (number of stickers used)
- If we reach state
-
Return -1 if impossible (queue empties without reaching goal state)
Why This Works:
- BFS guarantees we find the minimum number of stickers (shortest path)
- State compression allows efficient tracking of progress with just an integer
- The visited array ensures we don't explore the same state multiple times
- Greedy character collection within each sticker is optimal since using more characters from one sticker doesn't increase the sticker count
Time Complexity: O(m * 2^n * n)
where m
is the number of stickers and n
is the target length
Space Complexity: O(2^n)
for the visited array and queue
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Input:
- Stickers:
["ab", "bc", "ac"]
- Target:
"abc"
Goal: Find the minimum number of stickers to spell "abc"
State Representation:
- Target "abc" has 3 characters at positions 0, 1, 2
- State bitmask: bit 0 for 'a', bit 1 for 'b', bit 2 for 'c'
- Initial state:
000
(binary) = 0 - Goal state:
111
(binary) = 7
BFS Execution:
Level 0 (0 stickers used):
- Queue: [0]
- State 0 =
000
(no characters collected)
Level 1 (1 sticker used): Process state 0:
-
Try sticker "ab":
- Need 'a' at position 0? Yes (bit 0 = 0)
- Have 'a'? Yes → collect it, set bit 0
- Need 'b' at position 1? Yes (bit 1 = 0)
- Have 'b'? Yes → collect it, set bit 1
- Need 'c' at position 2? Yes (bit 2 = 0)
- Have 'c'? No
- New state:
011
= 3
-
Try sticker "bc":
- Need 'a'? Yes, but don't have it
- Need 'b'? Yes, have it → collect it, set bit 1
- Need 'c'? Yes, have it → collect it, set bit 2
- New state:
110
= 6
-
Try sticker "ac":
- Need 'a'? Yes, have it → collect it, set bit 0
- Need 'b'? Yes, but don't have it
- Need 'c'? Yes, have it → collect it, set bit 2
- New state:
101
= 5
Queue after Level 1: [3, 6, 5] Visited: {0, 3, 6, 5}
Level 2 (2 stickers used):
Process state 3 (011
- have 'a' and 'b', need 'c'):
- Try all stickers, only "bc" and "ac" can provide 'c'
- Using either gives us state
111
= 7 (goal reached!)
Result: Minimum 2 stickers needed
One optimal solution: Use "ab" first (getting 'a' and 'b'), then "ac" or "bc" (getting 'c').
Solution Implementation
1class Solution:
2 def minStickers(self, stickers: List[str], target: str) -> int:
3 """
4 Find minimum number of stickers needed to spell out the target string.
5 Uses BFS with bitmask to track which characters of target have been covered.
6
7 Args:
8 stickers: List of available sticker strings
9 target: Target string to spell out
10
11 Returns:
12 Minimum number of stickers needed, or -1 if impossible
13 """
14 target_length = len(target)
15
16 # Initialize BFS queue with empty state (no characters covered yet)
17 # State is represented as bitmask where bit i=1 means target[i] is covered
18 queue = deque([0])
19
20 # Track visited states to avoid revisiting
21 visited = [False] * (1 << target_length)
22 visited[0] = True
23
24 # Track number of stickers used (BFS level)
25 stickers_used = 0
26
27 # BFS to find minimum stickers needed
28 while queue:
29 # Process all states at current level
30 level_size = len(queue)
31 for _ in range(level_size):
32 current_state = queue.popleft()
33
34 # Check if all target characters are covered
35 if current_state == (1 << target_length) - 1:
36 return stickers_used
37
38 # Try applying each sticker to current state
39 for sticker in stickers:
40 # Count available characters in current sticker
41 sticker_chars = Counter(sticker)
42 next_state = current_state
43
44 # Try to use sticker characters to cover uncovered target positions
45 for position, char in enumerate(target):
46 # If position is uncovered and sticker has this character
47 if (current_state >> position & 1) == 0 and sticker_chars[char] > 0:
48 sticker_chars[char] -= 1
49 next_state |= 1 << position # Mark position as covered
50
51 # Add new state to queue if not visited
52 if not visited[next_state]:
53 visited[next_state] = True
54 queue.append(next_state)
55
56 # Increment sticker count after processing each level
57 stickers_used += 1
58
59 # Target cannot be formed with given stickers
60 return -1
61
1class Solution {
2 public int minStickers(String[] stickers, String target) {
3 int targetLength = target.length();
4
5 // Queue for BFS traversal, storing bitmask states
6 Deque<Integer> queue = new ArrayDeque<>();
7 queue.offer(0); // Start with empty state (no characters covered)
8
9 // Track visited states to avoid redundant processing
10 // Each bit represents whether a character in target is covered
11 boolean[] visited = new boolean[1 << targetLength];
12 visited[0] = true;
13
14 // BFS level by level, each level represents using one more sticker
15 for (int stickersUsed = 0; !queue.isEmpty(); stickersUsed++) {
16 int levelSize = queue.size();
17
18 // Process all states at current level
19 for (int i = 0; i < levelSize; i++) {
20 int currentState = queue.poll();
21
22 // Check if all target characters are covered
23 if (currentState == (1 << targetLength) - 1) {
24 return stickersUsed;
25 }
26
27 // Try each sticker
28 for (String sticker : stickers) {
29 // Count available characters in current sticker
30 int[] charCount = new int[26];
31 for (char ch : sticker.toCharArray()) {
32 charCount[ch - 'a']++;
33 }
34
35 // Build next state by using characters from this sticker
36 int nextState = currentState;
37 for (int j = 0; j < targetLength; j++) {
38 int charIndex = target.charAt(j) - 'a';
39
40 // If this position is not covered and sticker has this character
41 if ((currentState >> j & 1) == 0 && charCount[charIndex] > 0) {
42 charCount[charIndex]--;
43 nextState |= 1 << j; // Mark this position as covered
44 }
45 }
46
47 // Add new state to queue if not visited
48 if (!visited[nextState]) {
49 visited[nextState] = true;
50 queue.offer(nextState);
51 }
52 }
53 }
54 }
55
56 // Target cannot be formed with given stickers
57 return -1;
58 }
59}
60
1class Solution {
2public:
3 int minStickers(vector<string>& stickers, string target) {
4 int targetLength = target.size();
5
6 // BFS queue storing bitmask states (which characters of target are covered)
7 queue<int> bfsQueue{{0}};
8
9 // Track visited states to avoid redundant processing
10 // Each bit represents whether a character in target is covered
11 vector<bool> visited(1 << targetLength);
12 visited[0] = true;
13
14 // BFS level by level (each level represents using one more sticker)
15 for (int stickersUsed = 0; !bfsQueue.empty(); ++stickersUsed) {
16 int currentLevelSize = bfsQueue.size();
17
18 // Process all states at current level
19 for (int i = 0; i < currentLevelSize; ++i) {
20 int currentState = bfsQueue.front();
21 bfsQueue.pop();
22
23 // Check if all target characters are covered
24 if (currentState == (1 << targetLength) - 1) {
25 return stickersUsed;
26 }
27
28 // Try each sticker
29 for (const string& sticker : stickers) {
30 // Count frequency of each character in current sticker
31 int charFrequency[26]{};
32 for (char ch : sticker) {
33 ++charFrequency[ch - 'a'];
34 }
35
36 // Build next state by using current sticker
37 int nextState = currentState;
38 for (int j = 0; j < targetLength; ++j) {
39 int charIndex = target[j] - 'a';
40
41 // If this target character is not covered yet and sticker has it
42 if ((currentState >> j & 1) == 0 && charFrequency[charIndex] > 0) {
43 nextState |= 1 << j; // Mark this character as covered
44 --charFrequency[charIndex]; // Use one instance of this character
45 }
46 }
47
48 // Add new state to queue if not visited
49 if (!visited[nextState]) {
50 visited[nextState] = true;
51 bfsQueue.push(nextState);
52 }
53 }
54 }
55 }
56
57 // Target cannot be formed with given stickers
58 return -1;
59 }
60};
61
1/**
2 * Finds the minimum number of stickers needed to spell out the target string
3 * Uses BFS with bit masking to track which characters of target have been covered
4 *
5 * @param stickers - Array of sticker strings available to use
6 * @param target - The target string we want to spell out
7 * @returns Minimum number of stickers needed, or -1 if impossible
8 */
9function minStickers(stickers: string[], target: string): number {
10 const targetLength = target.length;
11
12 // BFS queue storing bitmask states (which target characters are covered)
13 const queue: number[] = [0];
14
15 // Track visited states to avoid reprocessing
16 const visited: boolean[] = Array(1 << targetLength).fill(false);
17 visited[0] = true;
18
19 // BFS level by level (each level represents using one more sticker)
20 for (let stickersUsed = 0; queue.length > 0; stickersUsed++) {
21 const nextLevelQueue: number[] = [];
22
23 // Process all states at current level
24 for (const currentState of queue) {
25 // Check if we've covered all characters in target
26 if (currentState === (1 << targetLength) - 1) {
27 return stickersUsed;
28 }
29
30 // Try each sticker
31 for (const sticker of stickers) {
32 // Count available characters in current sticker
33 const charCount: number[] = Array(26).fill(0);
34 for (const char of sticker) {
35 charCount[char.charCodeAt(0) - 97]++;
36 }
37
38 // Build next state by using characters from this sticker
39 let nextState = currentState;
40 for (let targetIndex = 0; targetIndex < targetLength; targetIndex++) {
41 const charIndex = target.charCodeAt(targetIndex) - 97;
42
43 // If this target position isn't covered yet and sticker has this character
44 if (((currentState >> targetIndex) & 1) === 0 && charCount[charIndex] > 0) {
45 // Mark this position as covered
46 nextState |= 1 << targetIndex;
47 // Use one instance of this character from sticker
48 charCount[charIndex]--;
49 }
50 }
51
52 // Add new state to queue if not visited
53 if (!visited[nextState]) {
54 visited[nextState] = true;
55 nextLevelQueue.push(nextState);
56 }
57 }
58 }
59
60 // Move to next level
61 queue.splice(0, queue.length, ...nextLevelQueue);
62 }
63
64 // Target cannot be spelled with given stickers
65 return -1;
66}
67
Time and Space Complexity
Time Complexity: O(2^n × m × (l + n))
The algorithm uses BFS to explore different states represented by bitmasks. There are 2^n
possible states (each bit represents whether a character at position i in target has been covered). For each state, we iterate through all m
stickers. For each sticker, we:
- Create a counter from the sticker string, which takes
O(l)
time wherel
is the average length of stickers - Iterate through all
n
positions in the target string to check if we can use characters from the current sticker
Therefore, the total time complexity is O(2^n × m × (l + n))
.
Space Complexity: O(2^n)
The space is dominated by:
- The
vis
array which tracks visited states:O(2^n)
- The queue which in the worst case can contain all states:
O(2^n)
- The counter for each sticker is created temporarily and doesn't affect the overall complexity
Thus, the space complexity is O(2^n)
.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Inefficient Sticker Filtering
A major performance pitfall is trying to use stickers that don't contain any characters needed by the target. This wastes computation time exploring states that can never lead to a solution.
Problem Example:
# If target = "abc" and we have stickers = ["xyz", "def", "abc"] # The sticker "xyz" will never contribute to the solution # But without filtering, we still process it at every BFS level
Solution: Pre-filter stickers to only keep those that contain at least one character from the target:
def minStickers(self, stickers: List[str], target: str) -> int:
target_chars = set(target)
# Filter out useless stickers
useful_stickers = []
for sticker in stickers:
if any(c in target_chars for c in sticker):
useful_stickers.append(sticker)
# Check if target is achievable
all_sticker_chars = set(''.join(useful_stickers))
if not all(c in all_sticker_chars for c in target):
return -1
# Continue with BFS using only useful_stickers...
2. Not Checking Early for Impossible Cases
The code might run through the entire BFS exploration even when it's impossible to form the target from the given stickers.
Problem Example:
# If target = "abc" but stickers = ["aaa", "bbb"] # We're missing 'c' entirely, so it's impossible # Without early checking, BFS will exhaust all states
Solution: Check if all target characters exist in at least one sticker before starting BFS:
def minStickers(self, stickers: List[str], target: str) -> int:
# Create set of all available characters from all stickers
available_chars = set()
for sticker in stickers:
available_chars.update(sticker)
# Early return if any target character is not available
for char in target:
if char not in available_chars:
return -1
# Proceed with BFS...
3. Redundant State Transitions
Using a sticker that doesn't add any new characters to the current state creates redundant transitions and slows down the algorithm.
Problem Example:
# Current state has already collected 'a' and 'b' # Using sticker "ab" won't change the state # But we still add it to the queue (though visited check prevents reprocessing)
Solution: Skip stickers that don't contribute any new characters:
for sticker in stickers:
sticker_chars = Counter(sticker)
next_state = current_state
state_changed = False # Track if this sticker adds anything new
for position, char in enumerate(target):
if (current_state >> position & 1) == 0 and sticker_chars[char] > 0:
sticker_chars[char] -= 1
next_state |= 1 << position
state_changed = True # Mark that we made progress
# Only add to queue if the sticker actually contributed
if state_changed and not visited[next_state]:
visited[next_state] = True
queue.append(next_state)
4. Memory Optimization for Large Targets
For targets with length > 20, the space requirement of 2^n
becomes prohibitive (over 1 million states).
Solution: Use a set instead of a boolean array for visited states, as most states won't be visited:
def minStickers(self, stickers: List[str], target: str) -> int:
if len(target) > 20:
# Use set for sparse state tracking
visited = {0} # Use set instead of array
# In BFS loop:
if next_state not in visited:
visited.add(next_state)
queue.append(next_state)
else:
# Use array for dense state tracking (original approach)
visited = [False] * (1 << len(target))
These optimizations can significantly improve both time and space efficiency, especially for edge cases and larger inputs.
Which of the following is a min heap?
Recommended Readings
Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
Want a Structured Path to Master System Design Too? Don’t Miss This!