567. 字符串的排列

题目

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

难度：🌟🌟🌟

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

示例 2：

输入：s1= "ab" s2 = "eidboaoo"
输出：false
 
提示：
1 <= s1.length, s2.length <= 10⁴
s1 和 s2 仅包含小写字母

题解

和子数组/子字符串相关的题目，很可能就是要考察滑动窗口算法。
写在滑动窗口框架模版后，主要是思考新增窗口和缩小窗口的条件什么，什么时候更新数据。
注意事项：

1. 本题在返回结果时，注意判断条件不是 valid == s1Len，而是 valid == len(need) ，因为 s1 中可能存在相同字符，导致 s1 的长度和 map 长度不一定相等。

代码实现

func checkInclusion(s1 string, s2 string) bool {
	need := make(map[byte]int)
	window := make(map[byte]int)
	s1Len := len(s1)
	for i := 0; i < len(s1); i++ {
		need[s1[i]]++
	}
	left, right := 0, 0
	valid := 0
	for right < len(s2) {
		c := s2[right]
		right++
		if _, ok := need[c]; ok { // 如果 c 在 need 中，则新增
			window[c]++
			// 更新窗口数据
			if window[c] == need[c] {
				valid++
			}
		}

		// 缩小窗口操作
		for (right - left) >= s1Len {
			if valid == len(need) {
				return true
			}
			d := s2[left]
			left++
			if _, ok := need[d]; ok { // 如果 d 在 need 中，则减少
				if window[d] == need[d] {
					valid--
				}
				window[d]--
			}
		}
	}
	return false
}