Stickers to spell word

Array Hash Table String Dynamic Programming Backtracking Bit Manipulation Memoization Bitmask

50.6% acceptance

Feb 20, 2026

1334

130

Given stickers and a target string, return minimum stickers to spell target. Return -1 if impossible.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_stickers(stickers: Vec<String>, target: String) -> i32 {
    let t: Vec<u8> = target.bytes().map(|b| b - b'a').collect();
    let n = t.len();
    let full = 1 << n;
    let mut dp = vec![i32::MAX; full];
    dp[0] = 0;

    // Precompute sticker char counts for target chars only
    let sticker_counts: Vec<Vec<i32>> = stickers.iter().map(|s| {
      let mut cnt = vec![0i32; 26];
      for b in s.bytes() { cnt[(b - b'a') as usize] += 1; }
      cnt
    }).collect();

    for state in 0..full {
      if dp[state] == i32::MAX { continue; }
      if state == full - 1 { continue; }
      // Find first unset bit
      let first = (0..n).find(|&i| state & (1 << i) == 0).unwrap();
      for sc in &sticker_counts {
        if sc[t[first] as usize] == 0 { continue; }
        let mut nstate = state;
        let mut rem = sc.clone();
        for i in 0..n {
          if nstate & (1 << i) == 0 && rem[t[i] as usize] > 0 {
            rem[t[i] as usize] -= 1;
            nstate |= 1 << i;
          }
        }
        if dp[nstate] > dp[state] + 1 {
          dp[nstate] = dp[state] + 1;
        }
      }
    }
    if dp[full - 1] == i32::MAX { -1 } else { dp[full - 1] }
  }
}