Minimum window substring

Hash Table String Sliding Window

47.0% acceptance

Jan 12, 2026

20026

849

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "". The testcases will be generated such that the answer is unique.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_window(s: String, t: String) -> String {
    let s = s.as_bytes();
    let t = t.as_bytes();
    
    // Use fixed-size arrays instead of HashMap for better performance
    let mut target = [0i32; 128];
    let mut required = 0;
    
    for &c in t {
      if target[c as usize] == 0 {
        required += 1;
      }
      target[c as usize] += 1;
    }
    
    let mut window = [0i32; 128];
    let mut left = 0;
    let mut min_len = usize::MAX;
    let mut min_start = 0;
    let mut formed = 0;
    
    for right in 0..s.len() {
      let c = s[right] as usize;
      window[c] += 1;
      
      if target[c] > 0 && window[c] == target[c] {
        formed += 1;
      }
      
      while formed == required {
        if right - left + 1 < min_len {
          min_len = right - left + 1;
          min_start = left;
        }
        
        let left_char = s[left] as usize;
        window[left_char] -= 1;
        if target[left_char] > 0 && window[left_char] < target[left_char] {
          formed -= 1;
        }
        left += 1;
      }
    }
    
    if min_len == usize::MAX {
      String::new()
    } else {
      unsafe { 
        // Safe: input strings are valid UTF-8
        std::str::from_utf8_unchecked(&s[min_start..min_start + min_len]).to_string()
      }
    }
  }
}