Stickers To Spell Word - Leetcode Solution

Problem Statement:

You want to spell a word using stickers. Each sticker has a lowercase English letter printed on it. You can use each sticker more than once, but you have to follow these rules:

You have to spell the given target word by using stickers only. You can use any number of stickers of any letter from the given set of stickers. If you use a sticker of a certain letter, you have to use all the stickers of that letter at once. You cannot use multiple stickers of two different letters to form a single letter. For example, in a set of stickers "aaaaaaaabbcc" you cannot form the letter "abc". Write a function to calculate the minimum number of stickers that you need to spell the target word. If it is impossible to spell the target word using the given set of stickers, return -1.

Solution:

The given problem can be solved using a greedy algorithm and dynamic programming.

First, we need to preprocess the given set of stickers and the target word to represent them in a suitable form for computation. We can represent the given sticker set as an array of size 26, where the ith element represents the count of the character 'a'+i in the sticker set. Similarly, we can represent the target word as an array of size 26, where the ith element represents the count of the character 'a'+i in the target word.

Then, we can use a recursive helper function to find out the minimum number of stickers required to spell the target word using the given set of stickers. The function takes as input the state of the sticker set and the target word and returns the minimum number of stickers required to spell the target word.

In each recursive call, we first check if the current state of the sticker set can form the target word. If the current state can form the target word, we return 0, as no stickers are required in this case. Otherwise, we iterate through all the characters in the target word and try to find a sticker that can form that character. For each character, we check if a sticker for that character is available in the sticker set. If it is available, we use that sticker and recursively calculate the minimum number of stickers required to spell the remaining characters in the target word. We return the minimum of all such values.

We can use dynamic programming to memoize the recursive calls and avoid redundant computation.

The final solution to the problem is obtained by calling the recursive helper function with the initial state of the sticker set and the target word.

Time Complexity:

The time complexity of the solution is O(2^N * M * K), where N is the length of the target word, M is the size of the sticker set, and K is the maximum count of any character in the given sticker set or the target word. The exponential term is due to the maximum number of recursive calls required. The M term is due to the iteration through the sticker set in each recursive call. The K term is due to the memoization of the recursive calls using a dictionary.

Space Complexity:

The space complexity of the solution is O(M * K), where M is the size of the sticker set and K is the maximum count of any character in the given sticker set or the target word. The space is required to store the sticker and target arrays, and the memoization dictionary.

Implementation:

Python implementation of the solution is given below.

def minStickers(stickers: List[str], target: str) -> int: sticker_counts = [0] * 26 target_counts = [0] * 26

for sticker in stickers:
    for char in sticker:
        sticker_counts[ord(char) - ord('a')] += 1
        
for char in target:
    target_counts[ord(char) - ord('a')] += 1
    
memo = {}

def helper(state, counts):
    if state == 0:
        return 0
    
    if state in memo:
        return memo[state]
    
    min_stickers = float('inf')
    
    for i in range(26):
        if counts[i] > 0 and sticker_counts[i] > 0:
            new_counts = counts[:]
            for j in range(26):
                new_counts[j] -= sticker_counts[i] * target_counts[j]
            new_state = sum([new_counts[j] << (5 * j) for j in range(26)])
            if new_state != state:
                stickers_required = helper(new_state, new_counts)
                if stickers_required != -1:
                    min_stickers = min(min_stickers, 1 + stickers_required)
    
    memo[state] = -1 if min_stickers == float('inf') else min_stickers
    return memo[state]

initial_state = sum([target_counts[i] << (5 * i) for i in range(26)])
return helper(initial_state, target_counts)

1