Stickers to Spell Word

Hard
1589.

Stickers to Spell Word

Stickers to Spell Word is a hard coding problem on strings, dynamic programming and backtracking, asked in Google and Meta interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} stickers
 * @param {string} target
 * @return {number}
 */
var minStickers = function(stickers, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Stickers to Spell Word — Solution in Python, Java & C++

Stickers to Spell Word solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Stickers to Spell Word is a hard coding problem on strings, dynamic programming and backtracking, asked in Google and Meta interviews.

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

Hints for Stickers to Spell Word

  1. Hint 1

    With at most 15 letters in target, a bitmask can record which positions of target are already covered.

  2. Hint 2

    From a mask, applying one sticker covers as many uncovered positions as its letters allow — this gives the next mask. Take the minimum number of steps from the empty mask to the full mask.

  3. Hint 3

    Big speed-up: the first uncovered position must be covered by some sticker eventually, and order does not matter, so only try stickers that contain that letter.

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]

Java

public static int minStickers(String[] stickers, String target) {
    int t = target.length();
    int full = (1 << t) - 1;
    int[][] counts = new int[stickers.length][26];
    for (int s = 0; s < stickers.length; s++)
        for (char ch : stickers[s].toCharArray()) counts[s][ch - 'a']++;
    int[] tg = new int[t];
    for (int i = 0; i < t; i++) tg[i] = target.charAt(i) - 'a';
    int INF = Integer.MAX_VALUE;
    int[] dp = new int[full + 1];
    Arrays.fill(dp, INF);
    dp[0] = 0;
    for (int mask = 0; mask < full; mask++) {
        if (dp[mask] == INF) continue;
        int first = 0;
        while (((mask >> first) & 1) == 1) first++;
        for (int[] c : counts) {
            if (c[tg[first]] == 0) continue;
            int[] left = c.clone();
            int nxt = mask;
            for (int p = 0; p < t; p++) {
                if (((nxt >> p) & 1) == 0 && 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];
}

C++

int minStickers(vector<string>& stickers, string target) {
    int t = target.size();
    int full = (1 << t) - 1;
    vector<array<int, 26>> counts;
    for (auto& s : stickers) {
        array<int, 26> c;
        c.fill(0);
        for (char ch : s) c[ch - 'a']++;
        counts.push_back(c);
    }
    const int INF = INT_MAX;
    vector<int> dp(full + 1, INF);
    dp[0] = 0;
    for (int mask = 0; mask < full; mask++) {
        if (dp[mask] == INF) continue;
        int first = 0;
        while ((mask >> first) & 1) first++;
        for (auto& c : counts) {
            if (c[target[first] - 'a'] == 0) continue;
            array<int, 26> left = c;
            int nxt = mask;
            for (int p = 0; p < t; p++) {
                int ch = target[p] - 'a';
                if (!((nxt >> p) & 1) && left[ch] > 0) {
                    left[ch]--;
                    nxt |= 1 << p;
                }
            }
            dp[nxt] = min(dp[nxt], dp[mask] + 1);
        }
    }
    return dp[full] == INF ? -1 : 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming