Stickers to Spell Word
Problem
Minimum stickers needed to spell `target` by picking characters from copies of each sticker.
stickers=['with','example','science'] target='thehat'3def min_stickers(stickers, target):
from collections import Counter
n = len(target); INF = 10**9; dp = [INF] * (1 << n); dp[0] = 0
for mask in range(1 << n):
if dp[mask] == INF: continue
for s in stickers:
sc = Counter(s); nm = mask
for i in range(n):
if not (nm >> i) & 1 and sc[target[i]] > 0:
sc[target[i]] -= 1; nm |= 1 << i
dp[nm] = min(dp[nm], dp[mask] + 1)
return dp[(1 << n) - 1] if dp[(1 << n) - 1] < INF else -1function minStickers(stickers, target) {
const n = target.length; const dp = new Array(1 << n).fill(Infinity); dp[0] = 0;
for (let mask = 0; mask < (1 << n); mask++) {
if (!isFinite(dp[mask])) continue;
for (const s of stickers) {
const sc = {}; for (const c of s) sc[c] = (sc[c]||0)+1;
let nm = mask;
for (let i = 0; i < n; i++)
if (!((nm >> i) & 1) && (sc[target[i]] || 0) > 0) { sc[target[i]]--; nm |= 1 << i; }
dp[nm] = Math.min(dp[nm], dp[mask] + 1);
}
}
return isFinite(dp[(1 << n) - 1]) ? dp[(1 << n) - 1] : -1;
}int minStickers(String[] stickers, String target) {
int n = target.length(); int[] dp = new int[1 << n];
Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0;
for (int mask = 0; mask < (1 << n); mask++) {
if (dp[mask] == Integer.MAX_VALUE) continue;
for (String s : stickers) {
int[] sc = new int[26]; for (char c : s.toCharArray()) sc[c - 'a']++;
int nm = mask;
for (int i = 0; i < n; i++) {
int c = target.charAt(i) - 'a';
if (((nm >> i) & 1) == 0 && sc[c] > 0) { sc[c]--; nm |= 1 << i; }
}
dp[nm] = Math.min(dp[nm], dp[mask] + 1);
}
}
return dp[(1 << n) - 1] == Integer.MAX_VALUE ? -1 : dp[(1 << n) - 1];
}int minStickers(vector& stickers, string target) {
int n = target.size(); vector dp(1 << n, INT_MAX); dp[0] = 0;
for (int mask = 0; mask < (1 << n); mask++) {
if (dp[mask] == INT_MAX) continue;
for (auto& s : stickers) {
int sc[26] = {0}; for (char c : s) sc[c - 'a']++;
int nm = mask;
for (int i = 0; i < n; i++) {
int c = target[i] - 'a';
if (!((nm >> i) & 1) && sc[c] > 0) { sc[c]--; nm |= 1 << i; }
}
dp[nm] = min(dp[nm], dp[mask] + 1);
}
}
return dp[(1 << n) - 1] == INT_MAX ? -1 : dp[(1 << n) - 1];
} Explanation
We want the fewest stickers needed to spell target, where each sticker is an unlimited bag of letters we can pull from. The smart move is to track which positions of the target are already filled using a bitmask: bit i set means target[i] is done.
dp[mask] is the minimum number of stickers to reach that set of filled positions. We start from dp[0] = 0 (nothing filled, zero stickers) and process masks in increasing order.
From a reachable mask we try each sticker. Using a letter count of the sticker, we greedily fill any still-empty target position whose letter the sticker can supply, producing a new mask nm. That new state costs one more sticker: dp[nm] = min(dp[nm], dp[mask] + 1).
Example: target = 'thehat'. Starting from the empty mask, applying sticker 'with' can fill the t and h positions, advancing the mask at a cost of 1. Repeating this with the best stickers reaches the full mask in 3 stickers.
The answer is dp[(1<<n) - 1] (all positions filled), or -1 if it stays unreachable. With n target characters there are 2^n masks, hence the O(2^n · stickers · n) cost.