Facebook Pixel

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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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 the i-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 position i 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:

  1. Initialize the queue with state 0 and mark it as visited

  2. Process level by level (each level represents using one more sticker):

    for _ in range(len(q)):  # Process all states at current level
  3. 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
  4. 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 bit i is 0 (character not collected)
    • cnt[c] > 0 checks if the sticker has this character available
    • nxt |= 1 << i sets bit i to 1 in the new state
  5. Add new states to the queue:

    • Only add unvisited states to avoid redundant exploration
    • Mark the new state as visited
  6. Check for completion:

    • If we reach state (1 << n) - 1, all characters are collected
    • Return the current level (number of stickers used)
  7. 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 Evaluator

Example 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 where l 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.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Which of the following is a min heap?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More