76.H 最小覆盖子串

题目

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

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

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length, t.length <= 105

• s 和 t 由英文字母组成

解题思路

滑动窗口法。

通过left和right指针维护一个窗口，找到一个包含所有t中字符的窗口之前，right指针一直右移，当找到包含所有t中字符的窗口之后，尝试将left指针右移，直到窗口不满足要求，或者left超过right为止。然后记录长度最小的窗口。

判断窗口是否包含所有t中字符的方法：维护两个map，ori维护t中的字符个数，cnt维护s中的字符个数，当且仅当cnt中每个字符的数量都不少于ori时，窗口包含t中所有字符。

实现代码

func minWindow(s string, t string) string {
	ori, cnt := map[byte]int{}, map[byte]int{}
	for i := 0; i < len(t); i++ {
		ori[t[i]]++
	}

	left, right := 0, 0
	resLen := len(s) + 1
	resLeft, resRight := -1, -1

	for left <= right && right < len(s) {
		if ori[s[right]] > 0 {
			cnt[s[right]]++
			for check(ori, cnt) && left <= right {
				newLen := right - left + 1
				if newLen < resLen {
					resLen = newLen
					resLeft = left
					resRight = right
				}

				if _, ok := cnt[s[left]]; ok {
					cnt[s[left]]--
				}
				left++
			}
		}
		right++
	}

	if resLeft == -1 {
		return ""
	}

	return s[resLeft:resRight+1]
}

func check(ori, cnt map[byte]int) bool {
	for k, v := range ori {
		if cnt[k] < v {
			return false
		}
	}
	return true
}