567. 字符串的排列

https://leetcode-cn.com/problems/permutation-in-string/

解法一：滑动窗口

由于子串是连续的，因此在滑动窗口模板的基础上，增加条件：当窗口>=t串时，左侧收缩

即可

class Solution:
    def checkInclusion(self, t: str, s: str) -> bool:
        need = {}
        window = {}
        for c in t:
            need[c] = need.get(c, 0)+1
        left = 0  # 窗口左边界
        right = 0  # 窗口右边界
        start = 0  # 记录子串起点

        valid = 0  # t串与s串匹配次数
        while right < len(s):
            # 增大窗口
            c = s[right]
            right += 1
            if c in need:  # 该字符在t串中
                window[c] = window.get(c, 0)+1
                if window[c] == need[c]:  # 该字符匹配
                    valid += 1
            while right-left >= len(t):
                if valid == len(need):
                    return True

                d = s[left]
                left += 1
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1

        return False