691. Stickers to Spell Word

HardBit ManipulationArrayStringDynamic ProgrammingBacktrackingBitmask

Problem Description

In this problem, we are provided with n different types of stickers, with each sticker containing a single lowercase English word. Our goal is to construct a specific target string by cutting out individual letters from these stickers and rearranging them. Importantly, we can use any number of stickers, and each type of sticker is available in an infinite quantity.

The key objective is to determine the minimum number of stickers that we need to use to spell out the entire target string. If it's not possible to construct the target string from the stickers provided, the function should return -1.

It is important to note that:

Each sticker can be used multiple times.
The target string is generated by concatenating random words from the 1000 most common US English words.
The task involves both optimisation (minimising the number of stickers used) and combination (cutting and rearranging sticker letters to form the target).

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

No: The problem does not involve nodes and edges as in graph problems.

Need to solve for kth smallest/largest?

No: The problem is focused on achieving a specific composition of letters using given stickers, not on sorting or selecting specific order statistics.

Involves Linked Lists?

No: It does not use data structures like linked lists.

Does the problem have small constraints?

Yes: The problem has constraints that are relatively manageable, such as small strings or limited number of stickers; thus, exploring many combinations is computationally feasible.

Brute force / Backtracking?

Yes: Backtracking is suitable here to systematically explore all different combinations of stickers to fulfill the required characters in the word.

Conclusion: The flowchart suggests using a backtracking approach for exploring combinations of stickers to build the target word.

Intuition

Finding the minimum number of stickers to form the target string can be broken down into exploring different combinations of sticker usage. The solution employs Breadth-First Search (BFS), a strategy used to traverse or search tree or graph data structures level by level.

Here's how the intuition develops:

States Representation Using Bit Masking: Treat each letter in the target string as a bit in a bitmask. If a letter is included, its corresponding bit is set to 1, otherwise it's 0. This allows an efficient representation of which characters are currently used to form the target.
Using a Queue for BFS: The queue stores states representing the letters from the target we have constructed at any step. Starting with no letters, the goal is to reach a state where all letters are obtained (all bits set to 1).
Processing Each Sticker: The algorithm examines how adding each sticker can change the current state. This involves checking if adding a letter from the sticker can fill in a missing bit in the state.
Avoiding Revisiting States: With potentially many stickers and target letters, the number of states can become large. Keeping track of visited states with a "visited" list ensures we don't process the same state multiple times.
Incrementing the Number of Stickers: Each level in the BFS represents the use of an additional sticker. The depth of the level (how many stickers used) increases until the target is reached or all options are exhausted.
Termination and Result: The search terminates when the full target is reached (all bits set to 1), or when no more states can be developed. The number of stickers (depth of BFS traversal) needed to accomplish the target is the answer, unless it is determined to be impossible, in which case -1 is returned.

In summary, the intuition behind the BFS approach is to explore all possible combinations of stickers incrementally and find the least number of stickers needed to create the target without revisiting the same intermediate states.

Learn more about Dynamic Programming, Backtracking and Bitmask patterns.

Solution Approach

The solution to this LeetCode problem employs a Breadth-First Search (BFS) approach. For BFS, we typically use a queue data structure, and here's how the provided solution leverages BFS along with other techniques:

Queue Initialization: We use Python's deque from the collections module to initialize a queue for our BFS which starts with an initial state of 0 signifying that no letters of the target have been used.
State Representation: The state of our approach is represented as an integer where each bit corresponds to a character in the target string. If the i-th bit is set, it means the i-th character of target is already constructed using the stickers.
Visited States Tracking: An array vis is initialized to keep track of which states have been visited to avoid redundant processing. Only unvisited states are pushed into the queue. Initially, only the state 0 is marked as visited (True).
Breadth-First Search: The solution uses a while-loop that continues until either the queue is empty or the target state ((1 << n) - 1, where all n bits are set meaning all characters of target are obtained) is achieved.
- Within the while-loop, a for-loop iterates over the current breadth of the queue, using queue.popleft() to examine states one by one.
- For every current state, the algorithm goes through each sticker and calculates the nxt state after possibly using this sticker. It uses a Counter object from Python's collections module to count the availability of characters in the sticker which assists in determining the eligibility of placing a character in the target.
- As it goes through the characters in the target, if it finds a character that is not yet used in the current state (checked using bitwise AND operation), and if the character is present in the sticker's Counter, it will update the nxt state by setting the corresponding bit (using bitwise OR operation) and decrementing the character's count in the counter.
State Transitions and Level Traversal: Whenever we encounter a new state (one that hasn't been visited), we mark it as visited and add it to the queue for further exploration. After examining all possible sticker applications for a given level, the ans (answer) variable is incremented since it would take one more sticker to potentially reach the target state at the next deeper level of our search.
Termination: If at some point the nxt state matches the target (all bits are set), we return the ans which represents the minimum number of stickers needed to achieve the target. If the queue is exhaustively processed without achieving the target, the function returns -1.
Algorithm Complexity: The solution is quite comprehensive in that it explores all possible combinations but maintains efficiency by avoiding revisiting states and by processing levels depth by depth, typical to BFS. The time complexity is substantial due to the combinatory nature, but by no means exponential to the point of being unfeasible, as the early termination and visited state pruning substantially reduce the search space.

In conclusion, the provided solution is a clear-cut application of BFS with a bitwise representation of states and an intricate handling of transitions using stickers to efficiently solve the problem of finding the minimum number of stickers to create the target string.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simple example to illustrate the solution approach. Suppose we have the following input:

Stickers: ["with", "example", "science"] Target: "wise"

Queue Initialization: We start by initializing an empty queue and push the initial state 0 into it, representing that none of the target letters are used yet.
State Representation: The target "wise" has four characters, each corresponding to a bit in our bitmask. Thus, "wise" corresponds to 1111 in binary when all characters are used.
Visited States Tracking: We have an array vis that starts filled with False values, and we set vis[0] to True to mark our initial state as visited.
Breadth-First Search:

We begin our BFS. Initially, the queue contains only the initial state 0 (0000 in binary, since none of the target's letters have been covered).
- We dequeue 0 and start examining our stickers. Let's start with the first sticker "with".
- The target is "wise", and the sticker "with" can contribute w and i to the target. We then update our state; w is the first bit and i is the second bit. Thus our state, after using the sticker "with", becomes 0110.
- We check our vis array and since this state is not visited, we mark it as visited (vis[0110] = True), then enqueue it.
- Next, we take the next sticker on the list, "example". It can contribute e. However, since we're considering the BFS level that started with state 0, adding "example" does not help us progress towards our target as we need either s or e at this point. Hence, it doesn't change the state.
- Finally, we consider the sticker "science" which can contribute s, i, and e, but we only care about s and e since i is already included from the "with" sticker. The state changes to 1111, which is our goal state.
State Transitions and Level Traversal: We found our target state at the first BFS level with just two stickers used: with and science. Therefore, we would not process the queue further and our ans would be 2.
Termination: Our traversal found the target state 1111, and we can return our answer 2. If we had not found our target, we would continue processing the queue, systematically using stickers at each level, and incrementing our sticker count until we either find the target or determine it is impossible.

In this example, our process was fairly straightforward as the target was reachable with a small number of sticker applications. In more complex cases, the breadth-first search would evaluate many more combinations by incrementing the state bit by bit until the target is fully constructed or found unattainable.

Solution Implementation

1from collections import deque, Counter
2
3class Solution:
4    def minStickers(self, stickers: List[str], target: str) -> int:
5        # Create a queue for breadth-first search and initialize it with an empty state.
6        queue = deque([0])
7        # Initialize the number of steps (minimum stickers) to 0.
8        steps = 0
9        # Calculate the length of the target word.
10        n = len(target)
11        # Create a visited states list to prevent repeated processing of the same state.
12        visited = [False] * (1 << n)
13        # Mark the empty state as visited.
14        visited[0] = True  
15      
16        # Start the breadth-first search.
17        while queue:
18            # Process all the states at the current level.
19            for _ in range(len(queue)):
20                current_state = queue.popleft()
21              
22                # If all characters are used, return the number of steps.
23                if current_state == (1 << n) - 1:
24                    return steps
25              
26                # Try all stickers for the current state.
27                for sticker in stickers:
28                    next_state = current_state
29                    sticker_count = Counter(sticker)
30                  
31                    # Attempt to match sticker characters with target characters.
32                    for i, char in enumerate(target):
33                        # If the character at position i is not yet added, and the sticker has the char.
34                        if not (next_state & (1 << i)) and sticker_count[char]:
35                            next_state |= 1 << i
36                            sticker_count[char] -= 1
37                          
38                    # If the next state has not been visited, mark it as visited and add to the queue.
39                    if not visited[next_state]:
40                        visited[next_state] = True
41                        queue.append(next_state)
42          
43            # Increment the step count after processing all states at the current level.
44            steps += 1
45      
46        # If target cannot be reached return -1 indicating not possible.
47        return -1
48

1class Solution {
2    public int minStickers(String[] stickers, String target) {
3        // Initialize a queue to store the states of characters from the target string
4        Deque<Integer> queue = new ArrayDeque<>();
5        queue.offer(0); // Start with an empty state (no characters covered)
6        int answer = 0; // Number of stickers used
7        int n = target.length(); // Length of the target string
8        boolean[] visited = new boolean[1 << n]; // Visited states to avoid repetition
9        visited[0] = true; // Mark the empty state as visited
10
11        // While there are states in the queue, continue processing
12        while (!queue.isEmpty()) {
13            // Process all states at the current level
14            for (int t = queue.size(); t > 0; --t) {
15                // Get and remove the current state from the queue
16                int currentState = queue.poll();
17                // If all characters are covered, return the count
18                if (currentState == (1 << n) - 1) {
19                    return answer;
20                }
21                // Try to cover more characters using each sticker
22                for (String sticker : stickers) {
23                    int nextState = currentState; // Start with the current state
24                    int[] charCount = new int[26]; // Frequency of each character in sticker
25                    for (char c : sticker.toCharArray()) {
26                        ++charCount[c - 'a'];
27                    }
28                    // Try to match sticker characters with uncovered characters in the target
29                    for (int i = 0; i < n; ++i) {
30                        int targetCharIndex = target.charAt(i) - 'a';
31                        // If the character at position i is not covered and
32                        // the sticker has the character, cover it and decrement the sticker's count
33                        if ((nextState & (1 << i)) == 0 && charCount[targetCharIndex] > 0) {
34                            nextState |= 1 << i;
35                            --charCount[targetCharIndex];
36                        }
37                    }
38                    // If the next state has not been visited, mark it as visited and add to queue
39                    if (!visited[nextState]) {
40                        visited[nextState] = true;
41                        queue.offer(nextState);
42                    }
43                }
44            }
45            // Increment the count after processing all states at the current level
46            ++answer;
47        }
48
49        // Return -1 if it's not possible to cover all the characters in the target string
50        return -1;
51    }
52}
53

1class Solution {
2public:
3    int minStickers(vector<string>& stickers, string target) {
4        // Initialize a queue that starts with the base state (no letters of the target are covered)
5        queue<int> statesQueue;
6        statesQueue.push(0);
7
8        // Variable to keep track of the number of stickers used
9        int numStickers = 0;
10
11        // Target string length
12        int targetLength = target.size();
13
14        // Boolean vector to keep track of visited states
15        vector<bool> visited(1 << targetLength, false);
16        visited[0] = true; // Starting state is visited
17
18        // BFS to find the minimum number of stickers needed
19        while (!statesQueue.empty()) {
20            // Process each state at the current level
21            for (int t = statesQueue.size(); t > 0; --t) {
22                int currentState = statesQueue.front();
23                statesQueue.pop();
24
25                // If all bits are set, we've covered all characters in the target
26                if (currentState == (1 << targetLength) - 1) return numStickers;
27
28                // Try to apply each sticker to this state
29                for (const auto& sticker : stickers) {
30                    int nextState = currentState;
31                    vector<int> letterCount(26, 0); // Count letters in the current sticker
32
33                    // Count the frequency of each letter in the sticker
34                    for (const char& c : sticker) {
35                        ++letterCount[c - 'a'];
36                    }
37
38                    // Try to use the sticker's letters to cover uncovered letters in the target
39                    for (int i = 0; i < targetLength; ++i) {
40                        int letterIndex = target[i] - 'a';
41                        if (!(nextState & (1 << i)) && letterCount[letterIndex] > 0) {
42                            // Set the corresponding bit if the letter can be covered
43                            nextState |= 1 << i;
44                            --letterCount[letterIndex];
45                        }
46                    }
47
48                    // If we've reached a new state, mark it as visited and add it to the queue
49                    if (!visited[nextState]) {
50                        visited[nextState] = true;
51                        statesQueue.push(nextState);
52                    }
53                }
54            }
55
56            // Increment the sticker count since a new level is processed
57            ++numStickers;
58        }
59
60        // If we've processed all states and didn't cover the whole target, return -1
61        return -1;
62    }
63};
64

1// Define a function to find the minimum number of stickers needed to form a target string.
2function minStickers(stickers: string[], target: string): number {
3    // Initialize a queue starting with the base state (no letters of the target are covered).
4    const statesQueue: number[] = [0];
5
6    // Variable to keep track of the number of stickers used.
7    let numStickers = 0;
8
9    // Target string length.
10    let targetLength = target.length;
11
12    // Boolean array to keep track of visited states.
13    let visited = new Array<boolean>(1 << targetLength).fill(false);
14    visited[0] = true; // Starting state is visited.
15
16    // Breadth-first search to find the minimum number of stickers needed.
17    while (statesQueue.length) {
18        // Process each state at the current level.
19        let levelSize = statesQueue.length;
20        for (let t = 0; t < levelSize; ++t) {
21            const currentState = statesQueue.shift() || 0;
22
23            // If all bits are set, we've covered all characters in the target.
24            if (currentState === (1 << targetLength) - 1) return numStickers;
25
26            // Try to apply each sticker to this state.
27            stickers.forEach(sticker => {
28                let nextState = currentState;
29                let letterCount = new Array<number>(26).fill(0); // Count letters in the current sticker.
30
31                // Count the frequency of each letter in the sticker.
32                for (const c of sticker) {
33                    letterCount[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
34                }
35
36                // Try to use the sticker's letters to cover uncovered letters in the target.
37                for (let i = 0; i < targetLength; ++i) {
38                    const letterIndex = target.charCodeAt(i) - 'a'.charCodeAt(0);
39                    if (!(nextState & (1 << i)) && letterCount[letterIndex] > 0) {
40                        // Set the corresponding bit if the letter can be covered.
41                        nextState |= 1 << i;
42                        letterCount[letterIndex]--;
43                    }
44                }
45
46                // If we've reached a new state, mark it as visited and add it to the queue.
47                if (!visited[nextState]) {
48                    visited[nextState] = true;
49                    statesQueue.push(nextState);
50                }
51            });
52        }
53
54        // Increment the sticker count since a new level is processed.
55        numStickers++;
56    }
57
58    // If we've processed all states and didn't cover the whole target, return -1.
59    return -1;
60}
61

Time and Space Complexity

The provided code performs a BFS (Breadth-First Search) over the states representing which characters of the target string have been covered by stickers. Each state is a bitmask of length n (where n is the length of the target string), with each bit representing whether the corresponding character in the target has been matched by a sticker.

Time Complexity

The time complexity of the algorithm can be estimated by considering the following:

The breadth of the BFS is 2^n, where n is the length of the target string, because there are 2^n possible states in the worst case (each bit in the bitmask can be either 0 or 1).
For each state, the algorithm iterates over all stickers, and then over each character in the target. Let m be the number of stickers, and k be the average length of a sticker.
For each sticker, it attempts to match characters to the target (n characters at most). During this process, it counts occurrences using a Counter, which takes O(k) time.
Upon matching characters, the algorithm updates the state and checks whether it has been visited before.

Therefore, the worst-case time complexity is O(2^n * m * n * k). This presumes that we could match every character in target with a character in a sticker every time, which represents the worst-case scenario for the number of operations needed.

Space Complexity

The space complexity of the algorithm is determined by:

The vis list, which stores whether a state has been visited (vis has a size of 2^n).
The q queue, which in the worst case could store all possible states (again, 2^n in size).
The Counter instance for each sticker, repeated for every state in the BFS. However, since the Counter is temporary and only stores up to k elements (where k is the average length of a sticker), this does not exceed O(k) space at any instance, and thus does not dominate the space complexity.

So the dominant factor is the space required to store all states, which results in a space complexity of O(2^n).

Learn more about how to find time and space complexity quickly using problem constraints.

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

Question 1 out of 10

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]

dp[i] = dp[i - 1] + 1

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

dp[i] = dp[i - 1]

I don’t know