LeetCode 691 - Stickers to Spell Word

LeetCode Problem 691

Difficulty: 🔴 Hard
Topics: Array, Hash Table, String, Dynamic Programming, Backtracking, Bit Manipulation, Memoization, Bitmask

Solution

Let's dive deep into a detailed technical solution guide for LeetCode 691, following your formatting rules exactly.

Problem Understanding

The problem asks us to construct a target string using letters cut from an unlimited supply of given stickers, where each sticker is a lowercase word. You can reuse stickers multiple times and rearrange letters freely. The goal is to find the minimum number of stickers required to form the target. If it is impossible, we must return -1.

The input consists of a list of stickers (each a word with lowercase letters) and a string target. The constraints are that there are at most 50 stickers, each sticker has at most 10 characters, and the target has at most 15 characters. These limits suggest that naive exhaustive search over all permutations of stickers will likely be too slow, and we should leverage optimizations such as memoization or bitmasking.

Key edge cases to consider include:

• The target contains letters not present in any sticker, which should return -1.
• The target or stickers contain repeated letters, which may require using the same sticker multiple times.
• The target itself is empty, which should return 0 as no stickers are needed.

Approaches

Brute Force

A naive brute-force solution would attempt all possible combinations of stickers recursively. For each recursive step, you subtract the letters of a chosen sticker from the current target and continue until the target is empty. Although this guarantees correctness, it is extremely slow because the number of possible sticker combinations grows exponentially with the target length and sticker count. With up to 50 stickers and a target length of 15, the recursion tree would be prohibitively large.

Optimal Approach

The key insight is that the problem can be solved efficiently using memoization with frequency counters. Instead of tracking individual letters in a string, we convert the target into a frequency count of letters. Each sticker is also represented as a frequency map. Then we recursively attempt to reduce the remaining target using stickers while memoizing previously computed subproblems.

Another optimization is to only consider stickers that contribute to the current target (i.e., contain at least one letter in the target). This reduces unnecessary computation.

By storing intermediate results in a hashmap keyed by the remaining letters (as a string or tuple of counts), we avoid recomputation, reducing the solution from exponential to manageable time complexity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^m)	O(m)	Recursively tries all sticker combinations, exponential in target length m
Optimal	O(2^m * n * 26)	O(2^m)	Uses memoization with frequency counters, only computes each subset of target once

Algorithm Walkthrough

1. Convert each sticker into a frequency array of size 26 representing counts of 'a' to 'z'. This allows constant-time subtraction and comparison with the target frequency.
2. Define a recursive function dp(remaining) where remaining is the current target as a string. If remaining is empty, return 0.
3. Check if remaining is already computed in the memo dictionary. If so, return the stored result.
4. Initialize min_stickers to infinity. For each sticker, check if it contains the first character of remaining. If not, skip it.
5. Subtract the sticker's letters from remaining to form a new next_remaining string. Recursively call dp(next_remaining) and add 1 for the current sticker. Update min_stickers with the minimum value.
6. Store the computed min_stickers in the memo dictionary keyed by remaining.
7. Return -1 if min_stickers is infinity (i.e., no solution), otherwise return min_stickers.

Why it works:

The memoization ensures each unique subset of letters is computed only once, avoiding exponential recomputation. By always subtracting sticker letters and considering only contributing stickers, the recursion efficiently narrows down possible solutions to the minimum number of stickers.

Python Solution

from collections import Counter
from typing import List

class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        n = len(stickers)
        sticker_counts = [Counter(sticker) for sticker in stickers]
        memo = {}

        def dp(remaining: str) -> int:
            if not remaining:
                return 0
            if remaining in memo:
                return memo[remaining]

            target_count = Counter(remaining)
            min_stickers = float('inf')

            for sticker in sticker_counts:
                if sticker[remaining[0]] == 0:
                    continue

                new_remaining = ''
                for ch in target_count:
                    if target_count[ch] > sticker[ch]:
                        new_remaining += ch * (target_count[ch] - sticker[ch])

                res = dp(new_remaining)
                if res != -1:
                    min_stickers = min(min_stickers, 1 + res)

            memo[remaining] = -1 if min_stickers == float('inf') else min_stickers
            return memo[remaining]

        return dp(target)

Explanation:

We first convert stickers into frequency counters for O(1) lookup of letters. The recursive dp function computes the minimum stickers for a given remaining string. Only stickers contributing to the first character are considered. After applying a sticker, we form a new remaining string and recursively solve it. Memoization ensures each unique string is computed once.

Go Solution

package main

func minStickers(stickers []string, target string) int {
    n := len(stickers)
    stickerCounts := make([][26]int, n)
    for i, s := range stickers {
        for _, ch := range s {
            stickerCounts[i][ch-'a']++
        }
    }

    memo := map[string]int{}

    var dp func(string) int
    dp = func(remaining string) int {
        if remaining == "" {
            return 0
        }
        if val, ok := memo[remaining]; ok {
            return val
        }

        targetCount := [26]int{}
        for _, ch := range remaining {
            targetCount[ch-'a']++
        }

        minStickers := 1 << 30
        for _, sticker := range stickerCounts {
            if sticker[remaining[0]-'a'] == 0 {
                continue
            }

            newRemaining := ""
            for i := 0; i < 26; i++ {
                if targetCount[i] > sticker[i] {
                    newRemaining += string(rune('a' + i)) * (targetCount[i] - sticker[i])
                }
            }

            res := dp(newRemaining)
            if res != -1 && 1+res < minStickers {
                minStickers = 1 + res
            }
        }

        if minStickers == 1<<30 {
            memo[remaining] = -1
        } else {
            memo[remaining] = minStickers
        }
        return memo[remaining]
    }

    return dp(target)
}

Go-specific notes:

We use arrays of length 26 instead of Counter for efficiency. String multiplication is simulated using loops or concatenation. Map memo caches results. Handling minStickers with 1 << 30 as infinity is typical in Go.

Worked Examples

Example 1: stickers = ["with","example","science"], target = "thehat"

1. Target count: t:2, h:2, e:1, a:1
2. Stickers frequency maps are computed.
3. Recursive calls:

• Use "with": reduces target to "hehat" → recursive
• Use "example": reduces remaining letters further

4. Minimum stickers found: 3

Example 2: stickers = ["notice","possible"], target = "basicbasic"

1. Target letters b, a, s, i, c
2. None of the stickers provide all required letters
3. Recursive search fails → return -1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(2^m * n * 26)	Each subset of the target string is solved at most once, n stickers considered per step, 26 letters for subtraction
Space	O(2^m + n * 26)	Memoization table stores up to 2^m subsets, plus sticker frequency arrays

The exponential in the target length is mitigated by memoization, making it feasible for target length ≤ 15.

Test Cases

# Basic examples
assert Solution().minStickers(["with","example","science"], "thehat") == 3  # Example 1
assert Solution().minStickers(["notice","possible"], "basicbasic") == -1   # Example 2

# Edge cases
assert Solution().minStickers(["a","b","c"], "abc") == 3  # Each letter requires a different sticker
assert Solution().minStickers(["abc"], "abc") == 1       # Single sticker covers all
assert Solution().minStickers(["abc"], "abcd") == -1     # Impossible target
assert Solution().minStickers(["aa","ab"], "aaa") == 2   # Need to reuse stickers
assert Solution().minStickers([], "a") == -1            # No stickers
assert