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.
- Difficulty: Hard
- Topics: Strings, Dynamic Programming, Backtracking, Bitmask
- Asked at: Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 501 <= stickers[i].length <= 101 <= target.length <= 15stickers[i] and target consist of lowercase English letters
Hints for Stickers to Spell Word
Hint 1
With at most 15 letters in
target, a bitmask can record which positions oftargetare already covered.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.
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
- Count the letters of every sticker once.
dp[0] = 0, every other entry infinite. For each mask in increasing order with a finitedp[mask], find its lowest uncovered positioni.- For each sticker containing
target[i], copy its letter counts and walk the uncovered positions, covering each one whose letter is still available; that yieldsnext. Relaxdp[next] = min(dp[next], dp[mask] + 1). - 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
targetappears on no sticker, the answer is -1 — the DP shows it as an unreachable full mask. - Repeated letters in
targetneed 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