Stamping the sequence

String Stack Greedy Queue

62.2% acceptance

Feb 25, 2026

1578

222

You are given two strings stamp and target. Initially, there is a string s of length target.length with all s[i] == '?'. In one turn, you can place stamp over s and replace every letter in the s with the corresponding letter from stamp. For example, if stamp = "abc" and target = "abcba", then s is "?????" initially. In one turn you can: place stamp at index 0 of s to obtain "abc??", place stamp at index 1 of s to obtain "?abc?", or place stamp at index 2 of s to obtain "??abc". Note that stamp must be fully contained in the boundaries of s in order to stamp (i.e., you cannot place stamp at index 3 of s). We want to convert s to target using at most 10 * target.length turns. Return an array of the index of the left-most letter being stamped at each turn. If we cannot obtain target from s within 10 * target.length turns, return an empty array.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn moves_to_stamp(stamp: String, target: String) -> Vec<i32> {
    let stamp: Vec<u8> = stamp.bytes().collect();
    let target: Vec<u8> = target.bytes().collect();
    let s_len = stamp.len();
    let t_len = target.len();
    let mut t = target.clone();
    let mut result = Vec::new();
    let mut total_q = 0usize;
    loop {
      let mut made_progress = false;
      for i in 0..=(t_len - s_len) {
        // Count how many chars match (non-'?' in t), and no conflicts
        let mut new_q = 0usize;
        let mut ok = true;
        for j in 0..s_len {
          if t[i+j] == b'?' { continue; }
          if t[i+j] != stamp[j] { ok = false; break; }
          new_q += 1;
        }
        if ok && new_q > 0 {
          made_progress = true;
          total_q += new_q;
          for j in 0..s_len { t[i+j] = b'?'; }
          result.push(i as i32);
          if total_q == t_len { 
            result.reverse();
            return result;
          }
        }
      }
      if !made_progress { return vec![]; }
    }
  }
}