最小覆盖子串 & 字符串的排列——滑动窗口

# 最小覆盖子串

这道题是需要从 s 中找到覆盖 t 中所有字符的最短子串，所以我们首先需要维护一个 map 去保存对应的字符出现次数，再用一个变量保存需要的字符数量，这样在搜索的时候可以快速知道是否满足要求。

利用滑动窗口，先扩张右边界，然后记数是否满足覆盖 t 的所有字符，如果满足则收缩左边界到刚好满足，然后重新将左边界导致不满足条件的字符纳入 map，然后重复这个过程即可。

```go
func minWindow(s string, t string) string {
    need := len(t)
    needCnt := [256]int{}
    for _, c := range []byte(t) {
        needCnt[c]++
    }
    l := 0
    start := 0
    res := math.MaxInt32
    for r := range s {
        if needCnt[s[r]] > 0 {
            need--
        }
        needCnt[s[r]]--
        for need == 0 {
            if r-l+1 < res {
                start = l
                res = r-l+1
            }
            needCnt[s[l]]++
            if needCnt[s[l]] > 0 {
                need++
            }
            l++
        }
    }
    if res == math.MaxInt32 {
        return ""
    }
    return s[start:start+res]
}
```

# 字符串的排列

这道题跟最小覆盖子串思路完全相同，只是终止条件不一样，最小覆盖子串需要在全局找到最短的覆盖所有字符的子串长度，而字符串的排列需要找到一个和s2字符串的字符频率完全相同的子串，也就是滑动窗口内不能有多余的字符，这一点也很简单 r-l+1 == len(s2) 即可。

```go
func checkInclusion(s1 string, s2 string) bool {
    if len(s1) > len(s2) {
        return false
    }
    need := len(s1)
    needCnt := [26]int{}
    for i := range s1 {
        needCnt[s1[i]-'a']++
    }
    l := 0
    for r := range s2 {
        c := s2[r]
        if needCnt[c-'a'] > 0 {
            need--
        }
        needCnt[c-'a']--
        for need == 0 {
            if r-l+1 == len(s1) {
                return true
            }
            needCnt[s2[l]-'a']++
            if needCnt[s2[l]-'a'] > 0 {
                need++
            }
            l++
        }
    }
    return false
}
```

Last modification：July 13, 2025