Find the lexicographically smallest valid sequence

Two Pointers String Dynamic Programming Greedy

21.6% acceptance

Feb 23, 2026

160

You are given two strings word1 and word2. A string x is called almost equal to y if you can change at most one character in x to make it identical to y. A sequence of indices seq is called valid if: The indices are sorted in ascending order. Concatenating the characters at these indices in word1 in the same order results in a string that is almost equal to word2. Return an array of size word2.length representing the lexicographically smallest valid sequence of indices. If no such sequence of indices exists, return an empty array. Note that the answer must represent the lexicographically smallest array, not the corresponding string formed by those indices.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn valid_sequence(word1: String, word2: String) -> Vec<i32> {
    let w1 = word1.as_bytes();
    let w2 = word2.as_bytes();
    let n = w1.len();
    let m = w2.len();

    // suffix_match[i] = how many chars of word2 from end can be matched from w1[i..] backwards
    // Specifically, suffix_match[i] = max j such that w1[i..] matches w2[j..m]
    // We compute: for each position in w1, the earliest suffix of w2 that can be matched from right
    let mut suffix = vec![m; n + 1];
    let mut j = m as i32 - 1;
    for i in (0..n).rev() {
      suffix[i] = suffix[i + 1];
      if j >= 0 && w1[i] == w2[j as usize] {
        suffix[i] = j as usize;
        j -= 1;
      }
    }
    // Actually recompute properly: suffix[i] = number of chars of w2's suffix matched starting from w1[i]
    // Let's use: right[i] = the index in w2 such that w2[right[i]..m] can be matched by w1[i..n]
    // We go from right to left
    let mut right = vec![m; n + 1];
    let mut rj = m;
    for i in (0..n).rev() {
      right[i] = right[i + 1];
      if rj > 0 && w1[i] == w2[rj - 1] {
        rj -= 1;
        right[i] = rj;
      }
    }

    // Now greedily pick smallest indices for word2 prefix
    let mut result = vec![0i32; m];
    let mut used_wildcard = false;
    let mut wi = 0usize; // index in w2
    let mut i = 0usize;  // index in w1
    while wi < m && i < n {
      if w1[i] == w2[wi] {
        result[wi] = i as i32;
        wi += 1;
        i += 1;
      } else if !used_wildcard {
        // Check: if we use wildcard here (change w1[i] to w2[wi]),
        // can we match the rest w2[wi+1..m] from w1[i+1..]?
        let remaining = m - wi - 1;
        if right[i + 1] <= wi + 1 {
          // Yes, the suffix w2[wi+1..] can be matched from w1[i+1..]
          result[wi] = i as i32;
          wi += 1;
          i += 1;
          used_wildcard = true;
        } else {
          i += 1;
        }
        let _ = remaining;
      } else {
        i += 1;
      }
    }
    if wi == m { result } else { vec![] }
  }
}