0076.最小覆盖子串

https://leetcode.cn/problems/minimum-window-substring/

方法一：滑动窗口

时间复杂度 $O(n+m)$，空间复杂度 $O(1)$，n 和 m 分别表示字符串 s 和 t 的长度。

func minWindow(s string, t string) string {
	need, window, cond := [256]int{}, [256]int{}, 0
	for i := 0; i < len(t); i++ {
		if need[t[i]] == 0 {
			cond++
		}
		need[t[i]]++
	}
	ans, m := s+" ", 0
	for i, j := 0, 0; j < len(s); j++ {
		window[s[j]]++
		if window[s[j]] == need[s[j]] {
			m++
		}
		if m < cond {
			continue
		}

		for m == cond {
			if len(ans) > j-i+1 {
				ans = s[i : j+1]
			}
			window[s[i]]--
			if window[s[i]] < need[s[i]] {
				m--
			}
			i++
		}
	}
	if len(ans) > len(s) {
		return ""
	}
	return ans
}

impl Solution {
    pub fn min_window(s: String, t: String) -> String {
        let (mut need, mut window) = ([0; 128], [0; 128]);
        let (s, t) = (s.as_bytes(), t.as_bytes());
        t.iter().for_each(|&v| {
            need[v as usize] += 1;
        });
        fn equal(need: &[i32; 128], window: &[i32; 128]) -> bool {
            for i in 0..128 {
                if need[i] != 0 && need[i] > window[i] {
                    return false;
                }
            }
            true
        }

        let mut ans: String = std::iter::repeat("0").take(s.len() + 1).collect();
        let mut pre = 0;
        for i in 0..s.len() {
            window[s[i] as usize] += 1;
            if !equal(&need, &window) {
                continue;
            }
            while equal(&need, &window) {
                if ans.len() > i - pre + 1 {
                    ans = String::from_utf8_lossy(&s[pre..=i]).to_string();
                }
                window[s[pre] as usize] -= 1;
                pre += 1;
            }
        }
        if ans.len() > s.len() {
            return "".to_string();
        }
        ans
    }
}