Minimum window subsequence

String Dynamic Programming Sliding Window

43.8% acceptance

Mar 31, 2026

1486

Given strings s1 and s2, return the minimum contiguous substring part of s1, so that s2 is a subsequence of the part. If there is no such window in s1 that covers all characters in s2, return the empty string "". If there are multiple such minimum-length windows, return the one with the left-most starting index.

Solution

Rust

Time O(n*m)

Space O(m)

LeetCode

solution.rs

impl Solution {
  pub fn min_window(s1: String, s2: String) -> String {
    let s1: Vec<u8> = s1.bytes().collect();
    let s2: Vec<u8> = s2.bytes().collect();
    let n = s1.len();
    let m = s2.len();

    // dp[j] = starting index in s1 of the current window matching s2[0..=j].
    // Iterating j right-to-left per character avoids reusing the same s1[i]
    // for multiple s2 positions (analogous to 0/1-knapsack row scan order).
    // Overall O(n*m) time, O(m) space.
    let mut dp: Vec<Option<usize>> = vec![None; m];
    let mut best_start = 0usize;
    let mut best_len = usize::MAX;

    for i in 0..n {
      for j in (0..m).rev() {
        if s1[i] == s2[j] {
          dp[j] = if j == 0 { Some(i) } else { dp[j - 1] };
        }
      }
      if let Some(start) = dp[m - 1] {
        let len = i - start + 1;
        if len < best_len {
          best_len = len;
          best_start = start;
        }
      }
    }

    if best_len == usize::MAX {
      String::new()
    } else {
      String::from_utf8(s1[best_start..best_start + best_len].to_vec()).unwrap()
    }
  }
}