Taro Logo

Stickers to Spell Word

Hard
Amazon logo
Amazon
1 view
Topics:
Dynamic Programming

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.

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.

How would you approach this problem? What data structures and algorithms would you use? Can you provide a detailed explanation of your solution and its time and space complexity?

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Can you provide an upper bound on the length of the target word and the number of stickers?
  2. Are the stickers and the target word guaranteed to consist only of lowercase English letters?
  3. If it's impossible to form the target word using the stickers, what should I return?
  4. Can a sticker be used multiple times, or is each sticker limited to only one use?
  5. If multiple solutions exist (different combinations of stickers that spell the target word), is any valid solution acceptable, or is there a criteria for choosing one (e.g., minimizing the number of stickers used)?

Brute Force Solution

Approach

The brute force strategy aims to discover the smallest number of stickers needed by exhaustively exploring all possible combinations of stickers. It's like trying every conceivable way to use the stickers until you spell out the target word. This involves checking every possible sticker, then every possible pair, then every possible group, and so on.

Here's how the algorithm would work step-by-step:

  1. First, consider each sticker individually and see if any single sticker contains all the letters needed for the target word.
  2. Next, consider all possible pairs of stickers and see if those two stickers combined contain all the letters needed. If not, discard this pair.
  3. Continue this process by considering all possible groups of three stickers, four stickers, and so on.
  4. For each group of stickers you consider, check if combining them allows you to spell the target word.
  5. Keep track of the smallest number of stickers required to spell the target word as you explore all these different combinations.
  6. When you've exhausted all possibilities (all single stickers, all pairs, all trios, etc.), the smallest number you've tracked is your answer.

Code Implementation

def stickers_to_spell_word_brute_force(stickers, target):
    minimum_stickers = float('inf')
    number_of_stickers = len(stickers)

    # Iterate through all possible combinations of stickers
    for i in range(1, 1 << number_of_stickers):
        current_stickers = []
        for j in range(number_of_stickers):
            if (i >> j) & 1:
                current_stickers.append(stickers[j])

        # Check if current combination can form the target
        combined_string = ''.join(current_stickers)
        can_form = can_form_target(combined_string, target)

        # If the combination spells the target and uses fewer stickers than current minimum, update
        if can_form:
            number_of_stickers_used = len(current_stickers)

            minimum_stickers = min(minimum_stickers, number_of_stickers_used)

    if minimum_stickers == float('inf'):
        return -1
    else:
        return minimum_stickers

def can_form_target(combined_string, target):
    target_counts = {}
    for char in target:
        target_counts[char] = target_counts.get(char, 0) + 1

    combined_counts = {}
    for char in combined_string:
        combined_counts[char] = combined_counts.get(char, 0) + 1

    # Check if all target characters are available in combined_string
    for char, count in target_counts.items():
        if char not in combined_counts or combined_counts[char] < count:
            return False #not enough characters

    return True

Big(O) Analysis

Time Complexity
O(m * 2^n)The brute force approach explores all possible subsets of stickers to find the minimum number needed to spell the target. Given n stickers, there are 2^n possible subsets (including the empty set). For each subset, we need to check if it can form the target word. The complexity of checking if a subset of stickers can form the target is driven by the length, m, of the target word (because in the worst case we have to look through all the target letters to see if they can be produced). Thus, the overall time complexity is approximately m * 2^n, which simplifies to O(m * 2^n).
Space Complexity
O(N!)The brute force strategy explores all possible combinations of stickers, which inherently involves generating subsets of the input sticker list. In the worst-case scenario, where we need to explore all possible groups of stickers, the number of combinations grows factorially with the number of stickers (N). Each combination of stickers potentially needs to be stored or processed, leading to a significant memory overhead. Therefore, the space complexity is dominated by the storage of these combinations, which can be up to O(N!).

Optimal Solution

Approach

The most efficient way to solve this problem is to use a technique called dynamic programming, combined with some smart pre-processing of the available stickers. We aim to minimize the number of stickers used by intelligently selecting which sticker to use at each step, building up our target word in the fewest moves possible.

Here's how the algorithm would work step-by-step:

  1. First, analyze each sticker to see which letters it contains and how many of each letter it has. Ignore stickers that don't contain any letters we need for our target word.
  2. Create a system to remember the best way to make partially completed target words. This is where dynamic programming comes in.
  3. Start with an empty target word (meaning we haven't used any letters yet).
  4. For each partially completed word, try using each sticker to see if it helps get closer to the full target word.
  5. When considering a sticker, determine which letters from the sticker can contribute to the target. Letters the target doesn't need are ignored.
  6. Calculate the new partially completed word that results from using that sticker. If we haven't reached the fully completed target word, keep track of whether using this sticker gets us closer to the target than other options we've tried before.
  7. If using this sticker leads to a new partially completed word that we've already seen, only keep track of it if using this sticker lets us reach it with fewer stickers than before.
  8. Repeat steps 4-7 until you get to the fully completed target word. The system keeping track of best ways ensures we only explore the most promising combinations.
  9. The minimum number of stickers needed to create the final word is the answer.

Code Implementation

def stickers_to_spell_word(stickers, target): 
    target_length = len(target)
    # Initialize DP table to store minimum stickers needed.
    dp = [-1] * (1 << target_length)
    dp[0] = 0

    for mask in range(1 << target_length):
        if dp[mask] == -1:
            continue

        for sticker in stickers:
            new_mask = mask
            sticker_letter_counts = {}
            for letter in sticker:
                sticker_letter_counts[letter] = sticker_letter_counts.get(letter, 0) + 1

            for letter_index in range(target_length):
                if (mask >> letter_index) & 1:
                    continue

                letter = target[letter_index]
                if letter in sticker_letter_counts and sticker_letter_counts[letter] > 0:
                    sticker_letter_counts[letter] -= 1
                    new_mask |= (1 << letter_index)

            # If the new mask is unchanged, the sticker did not help
            if new_mask > mask:
                if dp[new_mask] == -1 or dp[new_mask] > dp[mask] + 1:
                    dp[new_mask] = dp[mask] + 1

    return dp[(1 << target_length) - 1]

Big(O) Analysis

Time Complexity
O(m * 2^t + n * a)Let 'm' be the number of stickers and 't' be the length of the target word. The dynamic programming approach explores all possible subsets of characters needed to form the target word, leading to a factor of 2^t in the time complexity, multiplied by the number of stickers 'm' we might consider at each step. We also iterate through the available stickers of size 'n' and analyze each sticker taking 'a' amount of time, which can be further broken down but for simplicity, we can just write 'n * a' representing pre-processing or character counting operations. Therefore the overall time complexity is O(m * 2^t + n * a).
Space Complexity
O(26^T)The dynamic programming approach uses a system to remember the best way to make partially completed target words, essentially creating a table or memoization structure. The size of this table is determined by the number of possible partially completed words, where T is the length of the target word. In the worst case, each character in the target word can have up to 26 possible counts (assuming only lowercase letters and the need to track repetitions), leading to a space complexity proportional to 26 raised to the power of the length of the target word, T. Therefore, the auxiliary space used is O(26^T).

Edge Cases

CaseHow to Handle
Null or empty stickers arrayReturn -1 since the target cannot be formed from nothing.
Null or empty target stringReturn 0 since an empty target requires no stickers.
Stickers array contains an empty stringIgnore empty strings as they contribute nothing towards forming the target.
Target string contains characters not present in any stickerReturn -1 since the target can't be fully formed.
Stickers contain overlapping characters that could be used more efficiently in combinationThe solution explores all possible sticker combinations so the algorithm should naturally gravitate to the more efficient combination.
Target string is very long, leading to deep recursion (if using a recursive solution)Implement memoization to avoid recomputing solutions for the same target substring.
Large number of stickers with significant character overlapPrecompute the frequency of each character in each sticker to improve the efficiency of the matching process.
Integer overflow if tracking the minimum number of stickers requires a large integerUse a 64-bit integer or handle overflows by checking if the number of stickers exceeds a maximum allowed value and return -1 if it does.