Stickers to Spell Word — Hard Problem & Solution

Problem statement

Each sticker shows a lowercase word. You may buy any sticker as many times as you like, cut its letters apart, and rearrange letters from all the stickers you bought to spell target.

Return the minimum number of stickers you need to buy to spell target, or -1 if it is impossible.

Example 1

Input: stickers = ["with","example","science"], target = "thehat"
Output: 3
Explanation: Two "with" and one "example" give t, h, e, h, a, t.

Example 2

Input: stickers = ["notice","possible"], target = "basicbasic"
Output: -1
Explanation: No sticker has an `a`.

Example 3

Input: stickers = ["kai","ro","code"], target = "codekairo"
Output: 3

Constraints

• 1 <= stickers.length <= 50
• 1 <= stickers[i].length <= 10
• 1 <= target.length <= 15
• stickers[i] and target consist of lowercase English letters

How to solve Stickers to Spell Word

Shortest path over the 2^t subsets of target positions. Each sticker moves a mask to a superset, so processing masks in increasing numeric order is a valid DP order.

Approach

1. Count the letters of every sticker once.
2. dp[0] = 0, every other entry infinite. For each mask in increasing order with a finite dp[mask], find its lowest uncovered position i.
3. For each sticker containing target[i], copy its letter counts and walk the uncovered positions, covering each one whose letter is still available; that yields next. Relax dp[next] = min(dp[next], dp[mask] + 1).
4. Return dp[full], or -1 if it stayed infinite.

Why it works

Applying a sticker greedily covers the maximum number of positions possible for each letter, and positions holding the same letter are interchangeable, so nothing is lost by the greedy choice. Requiring the chosen sticker to cover the first uncovered position only fixes the order of the stickers in an optimal solution — some sticker in it covers that position, and it can be applied first.

Complexity

• Time — O(2^t · k · (t + 26)) for k stickers and target length t
• Space — O(2^t)

Pitfalls

• If a letter of target appears on no sticker, the answer is -1 — the DP shows it as an unreachable full mask.
• Repeated letters in target need repeated letters from stickers (or more stickers).
• Masks only grow, so iterating them in increasing order never reads a value before it is final.

Reference solution

Python

from typing import List

def minStickers(stickers: List[str], target: str) -> int:
    t = len(target)
    full = (1 << t) - 1
    counts = []
    for s in stickers:
        c = [0] * 26
        for ch in s:
            c[ord(ch) - 97] += 1
        counts.append(c)
    tg = [ord(ch) - 97 for ch in target]
    INF = float('inf')
    dp = [INF] * (full + 1)
    dp[0] = 0
    for mask in range(full + 1):
        if dp[mask] == INF:
            continue
        if mask == full:
            break
        first = 0
        while mask >> first & 1:
            first += 1
        for c in counts:
            if c[tg[first]] == 0:
                continue
            left = c[:]
            nxt = mask
            for i in range(t):
                if not (nxt >> i & 1) and left[tg[i]] > 0:
                    left[tg[i]] -= 1
                    nxt |= 1 << i
            if dp[mask] + 1 < dp[nxt]:
                dp[nxt] = dp[mask] + 1
    return -1 if dp[full] == INF else dp[full]

JavaScript

var minStickers = function(stickers, target) {
    var t = target.length;
    var full = (1 << t) - 1;
    var counts = stickers.map(function(s) {
        var c = new Array(26).fill(0);
        for (var i = 0; i < s.length; i++) c[s.charCodeAt(i) - 97]++;
        return c;
    });
    var tg = [];
    for (var i = 0; i < t; i++) tg.push(target.charCodeAt(i) - 97);
    var INF = 1e9;
    var dp = new Array(full + 1).fill(INF);
    dp[0] = 0;
    for (var mask = 0; mask < full; mask++) {
        if (dp[mask] === INF) continue;
        var first = 0;
        while ((mask >> first) & 1) first++;
        for (var s = 0; s < counts.length; s++) {
            var c = counts[s];
            if (c[tg[first]] === 0) continue;
            var left = c.slice();
            var nxt = mask;
            for (var p = 0; p < t; p++) {
                if (!((nxt >> p) & 1) && left[tg[p]] > 0) {
                    left[tg[p]]--;
                    nxt |= 1 << p;
                }
            }
            if (dp[mask] + 1 < dp[nxt]) dp[nxt] = dp[mask] + 1;
        }
    }
    return dp[full] === INF ? -1 : dp[full];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Zuma Game Hard
• Verbal Arithmetic Puzzle Hard
• Expression Add Operators Hard
• Word Search II Hard
• Similar String Groups Hard
• Longest Path With Different Adjacent Characters Hard