Stickers to Spell Word

• 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.

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.

1class Solution {2    private Map<String, Integer> memo;3    private int[][] stickerCounts;4 5    public int minStickers(String[] stickers, String target) {6        stickerCounts = new int[stickers.length][26];7        for (int i = 0; i < stickers.length; i++) {8            for (char c : stickers[i].toCharArray()) {9                stickerCounts[i][c - 'a']++;10            }11        }12        memo = new HashMap<>();13        memo.put("", 0);14        int result = solve(target);15        return result == Integer.MAX_VALUE ? -1 : result;16    }17 18    private int solve(String target) {19        if (memo.containsKey(target)) {20            return memo.get(target);21        }22 23        int minResult = Integer.MAX_VALUE;24        int[] targetCount = new int[26];25        for (char c : target.toCharArray()) {26            targetCount[c - 'a']++;27        }28 29        for (int[] stickerCount : stickerCounts) {30            if (stickerCount[target.charAt(0) - 'a'] == 0) {31                continue;32            }33 34            StringBuilder remainingTargetBuilder = new StringBuilder();35            for (int i = 0; i < 26; i++) {36                if (targetCount[i] > 0) {37                    int remaining = targetCount[i] - stickerCount[i];38                    for (int j = 0; j < remaining; j++) {39                        remainingTargetBuilder.append((char) ('a' + i));40                    }41                }42            }43            String remainingTarget = remainingTargetBuilder.toString();44            45            if (remainingTarget.length() < target.length()) {46                int res = solve(remainingTarget);47                if (res != Integer.MAX_VALUE) {48                    minResult = Math.min(minResult, 1 + res);49                }50            }51        }52 53        memo.put(target, minResult);54        return minResult;55    }56}

• 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.

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.

1class Solution {2    public int minStickers(String[] stickers, String target) {3        int tLen = target.length();4        int n = 1 << tLen;5        int[] dp = new int[n];6        Arrays.fill(dp, Integer.MAX_VALUE);7        dp[0] = 0;8 9        for (int mask = 0; mask < n; mask++) {10            if (dp[mask] == Integer.MAX_VALUE) {11                continue;12            }13 14            for (String sticker : stickers) {15                int nextMask = mask;16                int[] stickerCount = new int[26];17                for (char c : sticker.toCharArray()) {18                    stickerCount[c - 'a']++;19                }20 21                for (int i = 0; i < tLen; i++) {22                    if (((nextMask >> i) & 1) == 0) {23                        char c = target.charAt(i);24                        if (stickerCount[c - 'a'] > 0) {25                            nextMask |= (1 << i);26                            stickerCount[c - 'a']--;27                        }28                    }29                }30                31                if (nextMask != mask) {32                    dp[nextMask] = Math.min(dp[nextMask], dp[mask] + 1);33                }34            }35        }36 37        return dp[n - 1] == Integer.MAX_VALUE ? -1 : dp[n - 1];38    }39}