76. 最小覆盖子串

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

难度：🌟🌟🌟🌟

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

示例 2：

输入：s = "a", t = "a"
输出："a"

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
 
提示：

• 1 <= s.length, t.length <= 10⁵
• s 和 t 由英文字母组成

题解

这题难点在于窗口大小会灵活变动，不像一般的滑动窗口的窗口大小会固定不变。
因此我们每次向右滑动窗口的大小不能单独的 left++，这题的难点在于找到窗口缩小的判断条件 valid == len(need)，还有每次向右滑动多少，确定 left 滑动到哪。

代码实现

func minWindow(s string, t string) string {
	need := make(map[byte]int)
	window := make(map[byte]int)
	for i := 0; i < len(t); i++ {
		need[t[i]]++
	}
	left, right := 0, 0
	valid := 0
	res := "" // 记录结果
	for right < len(s) {
		c := s[right]
		right++
		if _, ok := need[c]; ok { // 如果 c 在 need 中存在，则新增
			window[c]++
			if window[c] == need[c] {
				valid++
			}
		}
		// 缩小窗口
		for valid == len(need) {
			d := s[left]
			if _, ok := need[d]; ok { // 如果 d 在 need 中存在，则整体向右滑动
				if window[d] == need[d] {
					valid--
				}
				window[d]--
				// 这里要确定 left 对应的值在 need 中存在
				p := s[left:right]
				if res == "" || len(p) < len(res) {
					res = p
				}
			}
			// 确定 left 滑动到哪，找到[left+1, right)中存在于 need 中的值的下标
			for i := left + 1; i < right; i++ {
				if _, ok := need[s[i]]; ok {
					left = i
					break
				}
			}
		}
	}
	return res
}