Stickers to Spell Word

How it works

We can represent the state as a bitmask where each bit indicates whether a character in the target has been covered. Starting from state 0 (no characters covered), we iterate through all states and for each sticker, compute which new state we can reach. This bottom-up approach systematically explores all possible ways to build the target.

Steps

1. Initialize a DP array of size 2^n (where n is target length), all set to -1 except dp[0] = 0.
2. Iterate through all states from 0 to 2^n - 1.
3. For each reachable state (dp[t] != -1), try applying each sticker.
4. For each sticker, compute the next state by marking which target characters get covered.
5. Update dp[nextState] to be the minimum of its current value and dp[t] + 1.
6. Return dp[2^n - 1], which represents all characters covered.

Complexity

• Time complexity: O(n * m * k *2 ^ n)
• Space complexity: O(2 ^ n)

Where n is the length of the target string, m is the number of stickers and k is the average length of each sticker.

Things to watch for

Forgetting That Stickers Can Be Reused

A common mistake is treating each sticker as a one-time use item. The problem explicitly states that stickers can be used infinitely many times. Your solution must allow revisiting the same sticker multiple times to cover repeated characters in the target.

Inefficient State Representation

Using the raw target string as the memoization key without normalization leads to redundant computation. Two different orderings of remaining characters (e.g., "abc" and "bac") represent the same problem state. Sorting the remaining string or using character frequency counts as the key significantly reduces the state space.

Not Pruning Useless Stickers

Trying every sticker at each step without filtering wastes time. If a sticker does not contain the first remaining character of the target, it cannot make progress toward completion. Always check that a sticker can contribute before recursing with it.

Incorrect Handling of the Impossible Case

Failing to detect when the target cannot be spelled leads to incorrect results or infinite loops. Before starting, verify that every character in the target appears in at least one sticker. During recursion, properly propagate infinity values when no valid solution exists for a subproblem.

Mutating Shared Data Structures

Modifying the sticker's character count map in place without creating a copy causes incorrect results across recursive branches. Always work with a fresh copy of the frequency map when simulating the use of a sticker to avoid corrupting state for sibling recursive calls.

from typing import List

class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        n = len(target)
        N = 1 << n
        dp = [-1] * N
        dp[0] = 0

        for t in range(N):
            if dp[t] == -1:
                continue
            for s in stickers:
                nextT = t
                for c in s:
                    for i in range(n):
                        if target[i] == c and not ((nextT >> i) & 1):
                            nextT |= 1 << i
                            break
                if dp[nextT] == -1 or dp[nextT] > dp[t] + 1:
                    dp[nextT] = dp[t] + 1
        return dp[N - 1]

class Solution {
public:
    int minStickers(vector<string>& stickers, string target) {
        int n = target.length();
        int N = 1 << n;
        vector<int> dp(N, -1);
        dp[0] = 0;

        for (int t = 0; t < N; t++) {
            if (dp[t] == -1) continue;
            for (string& s : stickers) {
                int nextT = t;
                for (char c : s) {
                    for (int i = 0; i < n; i++) {
                        if (target[i] == c && ((nextT >> i) & 1) == 0) {
                            nextT |= 1 << i;
                            break;
                        }
                    }
                }
                if (dp[nextT] == -1 || dp[nextT] > dp[t] + 1) {
                    dp[nextT] = dp[t] + 1;
                }
            }
        }

        return dp[N - 1];
    }
};