FrameWork

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新 e.g. window[c]++
        ...
       
        // 判断左侧窗口是否要收缩 这里的条件应该是
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新 e.g. window[d]--
            ...
        }
    }
}

func slidingWindow(s string, t string) {
	need, window := make(map[byte]int), make(map[byte]int)
	for i := 0; i < len(s); i++ {
		need[s[i]]++
	}
	left, right, valid := 0, 0, 0
	for right < len(s) {
		c := s[right]
		right++
		// ...
		for xxx {
			d := s[left]
			left++
			//...
		}
	}
}

使用模版考虑四个问题：

1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？

2、什么条件下，窗口应该暂停扩大，开始移动 left 缩小窗口？

3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？

4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

3. Longest Substring Without Repeating Characters

什么是滑动窗口？其实就是一个队列, 比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！如何移动？只要把队列的左边的元素移出就行了，直到满足题目要求！一直维持这样的队列，找出队列出现最长的长度时候，求出解！

func lengthOfLongestSubstring(s string) {
	window := make(map[byte]int)
	left, right, res := 0
	for right < len(s) {
		c := s[right]
		right++
		window[c]++
		for window[c] > 1 {
			d := s[left]
			left++
			window[d]--
		}
		res = max(res, right-left)
	}
	return res
}

76. Minimum Window Substring

// Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC"
func minWindow(s string, t string) string {
	// need window 分别记录 t 中字符出现次数(需凑齐)和窗口中对应字符出现次数
	need, window := make(map[byte]int), make(map[byte]int)
	for i := 0; i < len(s); i++ {
		need[s[i]]++
	}
	left, right, valid := 0, 0, 0 // valid: 窗口内有效的字符个数
	start, l := 0, math.MaxInt32  // 记录最小覆盖子串起始索引及长度
	for right < len(s) {
		c := s[right] // 即将移入窗口的字符
		right++
		if need[c] > 0 { // c 在目标串内,对窗口内数据更新
			window[c]++
			if window[c] == need[c] {
				valid++ // 已达到目标数目的字符
			}
		}
		for valid == len(need) { // 循环判断左侧窗口是否要收缩
			if right-left < l { // 更新最小覆盖子串
				start = left
				l = right - left
			}
			d := s[left]
			left++
			if need[d] > 0 { // 对窗口内数据更新
				if window[d] == need[d] {
					valid--
				}
				window[d]--
			}
		}
	}
	if l == math.MaxInt32 {
		return ""
	}
	return s[start : start+l]
}

159. 至多包含两个不同字符的最长子串

func lengthOfLongestSubstringTwoDistinct(s string) int {
    window := map[byte]int{}
    left, right, ans := 0, 0, 0
    for right < len(s) {
        window[s[right]]++
        right++
        for len(window) > 2 {
            window[s[left]]--
            if window[s[left]] == 0 {
                delete(window, s[left])
            }
            left++
        }
        ans = max(ans, right-left)
    }
    return ans
}

567. Permutation in String

// Input: s1 = "ab", s2 = "eidbaooo" Output: true
func checkInclusion(s1 string, s2 string) bool {
	need, window := make(map[byte]int), make(map[byte]int)
	for i := 0; i < len(s1); i++ {
		need[s1[i]]++
	}

	left, right, valid := 0, 0, 0
	for right < len(s2) {
		c := s2[right]
		right++
		if need[c] > 0 {
			window[c]++
			if window[c] == need[c] {
				valid++
			}
		}
		for right-left == len(s1) { // 判断左侧是否收缩, 将窗口控制在 len(s1)-1
			if valid == len(need) {
				return true
			}
			d := s2[left]
			left++
			if need[d] > 0 {
				if window[d] == need[d] {
					valid--
				}
				window[d]--
			}
		}
	}
	return false
}