76. Minimum Window Substring

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".

Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in s.

 

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Example 2:

Input: s = "a", t = "a"
Output: "a"

 

Constraints:

  • 1 <= s.length, t.length <= 105
  • s and t consist of English letters.

 

Follow up: Could you find an algorithm that runs in O(n) time?

Rust Solution

struct Solution;

impl Solution {
    fn min_window(s: String, t: String) -> String {
        let mut freq: Vec<usize> = vec![0; 256];
        let mut limit: Vec<usize> = vec![0; 256];
        let mut k = 0;
        let n = s.len();
        for b in t.bytes() {
            if limit[b as usize] == 0 {
                k += 1;
            }
            limit[b as usize] += 1;
        }
        let v: Vec<u8> = s.bytes().collect();
        let mut start = 0;
        let mut end = 0;
        let mut res = (std::usize::MAX, "");
        loop {
            if k == 0 {
                if end - start < res.0 {
                    res = (end - start, &s[start..end]);
                }
                if limit[v[start] as usize] != 0 {
                    if freq[v[start] as usize] == limit[v[start] as usize] {
                        k += 1;
                    }
                    freq[v[start] as usize] -= 1;
                }
                start += 1;
            } else {
                if end == n {
                    break;
                } else {
                    if limit[v[end] as usize] != 0 {
                        freq[v[end] as usize] += 1;
                        if freq[v[end] as usize] == limit[v[end] as usize] {
                            k -= 1;
                        }
                    }
                    end += 1;
                }
            }
        }
        res.1.to_string()
    }
}

#[test]
fn test() {
    let s = "ADOBECODEBANC".to_string();
    let t = "ABC".to_string();
    let res = "BANC".to_string();
    assert_eq!(Solution::min_window(s, t), res);
}

Having problems with this solution? Click here to submit an issue on github.