## 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.