leetcode76.最小覆盖子串

滑动窗口

leetcode76.最小覆盖子串

基本思路

1.窗口不断加入字符，扩大范围，直到找到符合条件的子串

2.窗口缩小，直到不符合条件，记得更新结果

3.重复1，2步，直到r达到字符串s的结尾

解法代码

func minWindow(s string, t string) string {
	need := make(map[byte]int, 0)
	window := make(map[byte]int, 0)

	for i, _ := range t {
		need[t[i]]++
	}

	l, r, start, lenght, valid := 0, 0, 0, math.MaxInt, 0

	for r < len(s) {
		c := s[r]
		r++
		if _, ok := need[c]; ok {
			window[c]++
			if window[c] == need[c] {
				valid++
			}
		}

		for valid == len(need) {
			if r-l < lenght {
				lenght = r - l
				start = l
			}
			d := s[l]
			l++

			if _, ok := need[d]; ok {
				if window[d] == need[d] {
					valid--
				}
				window[d]--
			}
		}
	}
	if lenght == math.MaxInt {
		return ""
	}
	return s[start : start+lenght]

}