691. Stickers to Spell Word - Detailed Explanation

Problem Statement

You are given an array of strings called stickers and a target string target. Each sticker consists of a set of characters that you can use to form words. You can use each sticker as many times as you like, but when you use a sticker, you must use it in its entirety (you get all its letters, but you can choose which letters to “apply” to cover the target). The goal is to determine the minimum number of stickers required to spell out the target word. If it is not possible to form the target word using the given stickers, return -1.

For example, if
stickers = ["ab", "bc"]
target = "abc"
One way to form "abc" is to use the sticker "ab" to cover 'a' and 'b', and then use the sticker "bc" to cover 'c' (note that the sticker "bc" provides 'b' as well, but that's extra). In this case, the minimum number of stickers needed is 2.

Hints

1. Preprocessing with Frequency Counts:
   Convert each sticker into a frequency count (i.e. a dictionary or an array of size 26) to quickly determine how many of each letter it contains.

2. Recursive Reduction:
   Think of the problem recursively: define a function dp(s) that returns the minimum number of stickers needed to form the string s. For each sticker, see how it can reduce the remaining letters needed to form s.

3. Memoization:
   Since many subproblems (substrings or remaining counts) will repeat during recursion, use a memoization technique (e.g., a dictionary in Python or a HashMap in Java) to cache and reuse results for subproblems.

4. Pruning Unhelpful Stickers:
   If a sticker does not contain any letter from the current target, you can skip it in that recursive call.

Approaches

Dynamic Programming with Recursion and Memoization

1. Convert Stickers to Frequency Counts:
   For each sticker, precompute an array (or dictionary) of size 26 representing the frequency of each letter.

2. Define the Recursive Function:
   Let dp(rem) be the minimum number of stickers required to form the remaining target string rem. If rem is empty, return 0.

3. Try Every Sticker:
   For each sticker, if it contains at least one character from rem, use it to reduce the count of the needed characters. Create a new “remaining” string after applying the sticker (by subtracting the sticker’s frequency from the frequency count of rem).

4. Memoize:
   Store the result for each unique remaining target (often represented as a string of counts or the remaining string itself) in a memoization cache. This prevents recomputation for the same subproblem.

5. Combine Results:
   The answer for dp(rem) is the minimum over all stickers of 1 + dp(new_remaining) (if using that sticker leads to progress). If no sticker can reduce rem, return -1 for that state.

Complexity Analysis

• Time Complexity:
  The worst-case time complexity is exponential in the length of the target due to the number of possible subproblems. However, memoization significantly reduces the number of states by caching results for each unique remaining target.

• Space Complexity:
  The memoization cache may store up to O(2^L) subproblems in the worst case (where L is the length of the target), and each state stores an answer. The frequency arrays use O(26) space per sticker.

Step-by-Step Walkthrough

1. Preprocessing:
   Convert each sticker into a frequency count. For example, if a sticker is "ab", its frequency count is [1,1,0,...,0].

2. Initial Call:
   Call dp(target) with the full target string. Convert the target into a frequency representation if needed.

3. Recursive Case:
   For the current target (e.g., "abc"), iterate through each sticker:

   • Skip the sticker if it has no common letters with the current target.
   • Otherwise, subtract the sticker’s letters from the target’s frequency count to form a new target string representing the remaining letters.
   • Recursively call dp(new_target) and add 1 (for using the current sticker).

4. Memoization:
   If the result for the current target has been computed before, return the cached value.

5. Combining Results:
   Choose the minimum number of stickers among all choices. If none of the stickers help reduce the target, return -1.

6. Return the Result:
   The result from dp(target) gives the minimum number of stickers required.

Python Code