# Stickers to Spell Word
**Difficulty:** HARD
[External](https://leetcode.com/problems/stickers-to-spell-word)
Canonical: https://scaleengineer.com/dsa/problems/stickers-to-spell-word
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Memoization](https://scaleengineer.com/dsa/patterns/memoization), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array, Hash Table, String
**Companies:** [IXL](https://scaleengineer.com/companies/ixl)
---
## Problem
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.length`
* `1 <= n <= 50`
* `1 <= stickers[i].length <= 10`
* `1 <= target.length <= 15`
* `stickers[i]` and `target` consist of lowercase English letters.

# Approaches
## Top-Down Dynamic Programming with Memoization
This approach uses recursion with memoization, a technique also known as top-down dynamic programming. The problem of finding the minimum stickers for a `target` is broken down into smaller subproblems: finding the minimum stickers for the remaining parts of the `target` after applying one sticker. To avoid re-calculating results for the same subproblem (e.g., needing to form `"ehat"` can be reached via multiple paths), we store the results in a memoization table (a hash map). The key for this table is the string of remaining characters, sorted canonically to ensure that different permutations are treated as the same state.
**Time:** O(S * N * T), where S is the number of states (subproblems), N is the number of stickers, and T is the length of the target. The number of states is bounded by `2^T`. For each state, we iterate through N stickers, and for each sticker, we perform an O(T) operation to generate the next state. This gives a total time complexity of O(2^T * N * T). · **Space:** O(S * T), where S is the number of subproblems and T is the maximum length of a subproblem's string representation. In the worst case, S can be up to `2^T` (where T is the length of the original target), making the space complexity O(2^T * T). This space is used for the memoization table and the recursion call stack.
**Pros:** Vastly more efficient than brute-force recursion by avoiding re-computation of subproblems.; The logic directly follows the recursive nature of the problem, making it relatively intuitive to design.; Guaranteed to find the optimal solution.
**Cons:** Can be slightly slower than an iterative bottom-up approach due to recursion overhead.; String manipulation for memoization keys can add overhead, although using a canonical representation is necessary.; For very deep recursion, it could potentially lead to a stack overflow error, though unlikely with the given constraints (T <= 15).
### Explanation
The core idea is to define a function `solve(currentTarget)` that computes the minimum stickers needed to spell `currentTarget`. 

To implement this, we first pre-process the input `stickers` into character frequency maps (e.g., `int[26]`) for quick lookups. The recursive function `solve` works as follows:

- **Base Case:** If the `currentTarget` string is empty, we've successfully spelled the original target. We need 0 more stickers, so we return 0.
- **Memoization:** We use a `HashMap<String, Integer>` to store results. Before computing, we check if the result for `currentTarget` is already stored. If so, we return it immediately.
- **Recursive Logic:** We iterate through every sticker. For each sticker, we determine which characters from `currentTarget` it can provide. We then generate a `remainingTarget` string. If this new string is shorter than `currentTarget`, we recursively call `solve(remainingTarget)`. The result for the current state is `1 +` the minimum result from all possible recursive calls. 

An important optimization is to only consider stickers that provide at least one of the characters we currently need. A simple way to enforce this is to only try stickers that contain the first character of the canonical (sorted) `currentTarget`. This guarantees that every sticker we use makes progress.

Finally, we store the computed minimum value in our memoization table before returning it. If after trying all stickers, we cannot reduce the target, we store infinity to signify that this path is a dead end.

```java
class Solution {
    private Map<String, Integer> memo;
    private int[][] stickerCounts;

    public int minStickers(String[] stickers, String target) {
        stickerCounts = new int[stickers.length][26];
        for (int i = 0; i < stickers.length; i++) {
            for (char c : stickers[i].toCharArray()) {
                stickerCounts[i][c - 'a']++;
            }
        }
        memo = new HashMap<>();
        memo.put("", 0);
        int result = solve(target);
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    private int solve(String target) {
        if (memo.containsKey(target)) {
            return memo.get(target);
        }

        int minResult = Integer.MAX_VALUE;
        int[] targetCount = new int[26];
        for (char c : target.toCharArray()) {
            targetCount[c - 'a']++;
        }

        for (int[] stickerCount : stickerCounts) {
            if (stickerCount[target.charAt(0) - 'a'] == 0) {
                continue;
            }

            StringBuilder remainingTargetBuilder = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                if (targetCount[i] > 0) {
                    int remaining = targetCount[i] - stickerCount[i];
                    for (int j = 0; j < remaining; j++) {
                        remainingTargetBuilder.append((char) ('a' + i));
                    }
                }
            }
            String remainingTarget = remainingTargetBuilder.toString();
            
            if (remainingTarget.length() < target.length()) {
                int res = solve(remainingTarget);
                if (res != Integer.MAX_VALUE) {
                    minResult = Math.min(minResult, 1 + res);
                }
            }
        }

        memo.put(target, minResult);
        return minResult;
    }
}
```
### Algorithm
*   **Preprocessing:** Convert each sticker word into a character frequency map (an array of 26 integers). This avoids repeated counting.
*   **Memoization:** Use a hash map `memo` to store the results of subproblems. The key will be the canonical representation of the remaining target characters (a sorted string), and the value will be the minimum number of stickers required.
*   **Recursive Function `solve(target)`:**
    1.  **Base Case:** If `target` is an empty string, 0 stickers are needed. Return 0.
    2.  **Memoization Check:** If `target` is already in `memo`, return the stored value.
    3.  **Recursive Step:**
        *   Initialize `minStickers` to a value representing infinity.
        *   Convert the current `target` string to a frequency map `targetCount`.
        *   Iterate through each pre-processed `stickerCount`.
        *   **Optimization:** To ensure progress, only consider stickers that contain the first character of the current (sorted) `target` string.
        *   For a useful sticker, calculate the `remainingTarget` by subtracting the sticker's characters from `targetCount`. Construct a new string from the remaining character counts. Since we build this string character by character from 'a' to 'z', it will be naturally sorted, providing a canonical key for the memoization table.
        *   If the `remainingTarget` is shorter than the current `target`, it means the sticker was helpful. Make a recursive call: `res = solve(remainingTarget)`.
        *   If `res` is not infinity, update `minStickers = min(minStickers, 1 + res)`.
    4.  **Save and Return:** Store `minStickers` in `memo` for the current `target` and return it.
*   **Initial Call:** The main function calls `solve(target)` and returns the result, or -1 if the result is infinity.

## Bottom-Up Dynamic Programming with Bitmasking
A more optimized and iterative solution can be achieved using bottom-up dynamic programming with bitmasking. This approach avoids recursion entirely. We use an array, say `dp`, where the index is a bitmask representing a subset of the characters in the `target` string. For a target of length `T`, we'll have `2^T` possible subsets (states). `dp[mask]` stores the minimum number of stickers required to form the subsequence represented by `mask`. We start with the base case `dp[0] = 0` (for an empty set of characters) and iteratively build up the solution for larger and larger subsets until we reach the state representing the full target string.
**Time:** O(2^T * N * T), where T is the length of the target and N is the number of stickers. We iterate through `2^T` masks. For each mask, we iterate through N stickers. For each sticker, we iterate through the T characters of the target to compute the next mask. · **Space:** O(2^T), where T is the length of the target. This space is dominated by the `dp` array of size `2^T`.
**Pros:** Generally faster than the recursive top-down approach due to its iterative nature, which avoids function call overhead and can have better cache performance.; Avoids potential stack overflow issues that can arise from deep recursion.; The space complexity is slightly better as it doesn't need to store string keys for a map, just the `dp` array.
**Cons:** The concept of bitmask DP can be less intuitive than a straightforward recursive approach.; The space complexity is exponential, `O(2^T)`, which is only feasible for small `T` (like `T <= 15` in this problem).
### Explanation
In this approach, we represent the state of our problem using a bitmask. A mask is an integer where the `i`-th bit corresponds to the `i`-th character of the `target` string. If the bit is 1, the character is covered; if it's 0, it's not.

We create a `dp` array of size `2^T`, where `T` is the length of `target`. `dp[mask]` will store the minimum stickers needed. We initialize `dp[0]` to 0 and all other entries to infinity.

The algorithm proceeds by iterating through each mask from 0 up to `(1<<T) - 1`. For each `mask` whose `dp` value is not infinity (meaning it's a reachable state), we try to apply each sticker to transition to a new state.

For a given `mask` and a sticker, we calculate the `nextMask`. We start with `nextMask = mask`. We then iterate through the `target`'s characters. If the `i`-th character is not yet covered in `mask` and the sticker has the required letter, we set the `i`-th bit in `nextMask` and use up one instance of that letter from the sticker. This greedy application of a sticker's letters is valid because the `dp` state only cares about *which* characters are covered, not *how* they were covered.

After determining the `nextMask`, we update its `dp` value with `dp[nextMask] = min(dp[nextMask], dp[mask] + 1)`. This means the cost to reach `nextMask` is potentially the cost to reach `mask` plus one more sticker.

After all masks have been processed, `dp[(1<<T) - 1]` will contain the minimum number of stickers to cover all characters of the target. If the value remains infinity, the target is unreachable.

```java
class Solution {
    public int minStickers(String[] stickers, String target) {
        int tLen = target.length();
        int n = 1 << tLen;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int mask = 0; mask < n; mask++) {
            if (dp[mask] == Integer.MAX_VALUE) {
                continue;
            }

            for (String sticker : stickers) {
                int nextMask = mask;
                int[] stickerCount = new int[26];
                for (char c : sticker.toCharArray()) {
                    stickerCount[c - 'a']++;
                }

                for (int i = 0; i < tLen; i++) {
                    if (((nextMask >> i) & 1) == 0) {
                        char c = target.charAt(i);
                        if (stickerCount[c - 'a'] > 0) {
                            nextMask |= (1 << i);
                            stickerCount[c - 'a']--;
                        }
                    }
                }
                
                if (nextMask != mask) {
                    dp[nextMask] = Math.min(dp[nextMask], dp[mask] + 1);
                }
            }
        }

        return dp[n - 1] == Integer.MAX_VALUE ? -1 : dp[n - 1];
    }
}
```
### Algorithm
*   **State Representation:** Use a bitmask of length `T` (length of `target`) to represent a subproblem. `dp[mask]` will store the minimum stickers needed to form the subsequence of `target` where the `i`-th bit of `mask` is 1 if the `i`-th character is formed.
*   **Initialization:** Create a `dp` array of size `2^T`. Initialize `dp[0] = 0` (0 stickers for an empty sequence) and all other `dp` entries to infinity.
*   **Preprocessing:** As before, convert stickers to character frequency maps (`int[26]`).
*   **Iteration:**
    1.  Iterate through each `mask` from `0` to `2^T - 1`.
    2.  If `dp[mask]` is infinity, it's an unreachable state, so skip it.
    3.  For the current `mask`, iterate through each sticker.
    4.  Calculate the `nextMask` that would result from applying the current sticker to the state represented by `mask`.
        *   Start with `tempMask = mask`.
        *   Make a copy of the sticker's frequency map.
        *   Iterate through the `target` string from `i = 0` to `T-1`.
        *   If the `i`-th character is needed (`(tempMask >> i) & 1 == 0`) and the sticker can provide it, set the `i`-th bit in `tempMask` and decrement the character's count from the sticker's copied map.
    5.  After applying the sticker, we have a `nextMask`. Update the `dp` table: `dp[nextMask] = min(dp[nextMask], dp[mask] + 1)`.
*   **Result:** The final answer is `dp[(1<<T) - 1]`. If it's infinity, the target is impossible. Return -1.

# Solutions
### Java

```java
class Solution { public int minStickers ( String [] stickers , String target ) { Deque < Integer > q = new ArrayDeque <>(); q . offer ( 0 ); int ans = 0 ; int n = target . length (); boolean [] vis = new boolean [ 1 << n ]; vis [ 0 ] = true ; while (! q . isEmpty ()) { for ( int t = q . size (); t > 0 ; -- t ) { int state = q . poll (); if ( state == ( 1 << n ) - 1 ) { return ans ; } for ( String s : stickers ) { int nxt = state ; int [] cnt = new int [ 26 ]; for ( char c : s . toCharArray ()) { ++ cnt [ c - 'a' ]; } for ( int i = 0 ; i < n ; ++ i ) { int idx = target . charAt ( i ) - 'a' ; if (( nxt & ( 1 << i )) == 0 && cnt [ idx ] > 0 ) { nxt |= 1 << i ; -- cnt [ idx ]; } } if (! vis [ nxt ]) { vis [ nxt ] = true ; q . offer ( nxt ); } } } ++ ans ; } return - 1 ; } }
```

### CPP

```cpp
class Solution { public: int minStickers ( vector < string >& stickers , string target ) { queue < int > q { { 0 } }; int ans = 0 ; int n = target . size (); vector < bool > vis ( 1 << n ); vis [ 0 ] = true ; while ( ! q . empty ()) { for ( int t = q . size (); t ; -- t ) { int state = q . front (); if ( state == ( 1 << n ) - 1 ) return ans ; q . pop (); for ( auto & s : stickers ) { int nxt = state ; vector < int > cnt ( 26 ); for ( char & c : s ) ++ cnt [ c - 'a' ]; for ( int i = 0 ; i < n ; ++ i ) { int idx = target [ i ] - 'a' ; if ( ! ( nxt & ( 1 << i )) && cnt [ idx ]) { nxt |= 1 << i ; -- cnt [ idx ]; } } if ( ! vis [ nxt ]) { vis [ nxt ] = true ; q . push ( nxt ); } } } ++ ans ; } return - 1 ; } };
```

### Python

```python
class Solution : def minStickers ( self , stickers : List [ str ], target : str ) -> int : q = deque ([ 0 ]) ans = 0 n = len ( target ) vis = [ False ] * ( 1 << n ) vis [ 0 ] = True while q : for _ in range ( len ( q )): state = q . popleft () if state == ( 1 << n ) - 1 : return ans for s in stickers : nxt = state cnt = Counter ( s ) for i , c in enumerate ( target ): if not ( nxt & ( 1 << i )) and cnt [ c ]: nxt |= 1 << i cnt [ c ] -= 1 if not vis [ nxt ]: vis [ nxt ] = True q . append ( nxt ) ans += 1 return - 1
```