【经典LeetCode算法题目专栏分类】【第8期】滑动窗口：最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串

left = 0
right  = 0
while  right < len(s):
    # 右指针右移增大窗口
    window.add(s[right])
    right  += 1
    while isvalid:
        # 当满足某种条件时开始从左边收缩窗口
        window.remove(s[left])
        left += 1

def slidingWindow(s, t):
    from collections import defaultdict
    # defaultdict(int)对于不存在的键默认值为0，
    # 可以直接进行window[c] += 1的操作，免去了判断过程
    window = defaultdict(int)
    needs  = defaultdict(int)
    left = 0
    right = 0
    for c in t:
        needs[c] += 1
    while right < len(s):
        # c1为移入窗口的字符
        c1 = s[right]
        # 窗口右移
        right += 1
        # 进行窗口内数据的相关操作
        # TODO
        # 判断左侧窗口是否要收缩
        while window needs shrink:
            # c2为将要移出窗口的字符
            c2 = s[left]
            # 左指针右移，收缩窗口
            left += 1
            # 进行窗口内数据的相关操作
            # TODO

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import defaultdict
        needs = defaultdict(int)
        window = defaultdict(int)
        left = 0
        right = 0
        count = 0 #window中满足条件的字符数
        start = 0 #记录最小子串的起始位置
        min_len = float('inf') #记录最小子串的长度
        for c in t:
            needs[c] += 1
        while right < len(s):
            c1 = s[right]
            right += 1
            if  c1 in needs:
                window[c1] += 1
                if window[c1] == needs[c1]:
                    count += 1
            while count == len(needs):
                # 更新最小覆盖子串
                if right - left < min_len:
                    start = left
                    min_len = right - left
                c2 = s[left]
                left += 1
                if c2 in needs:
                    window[c2] -= 1
                    if window[c2] < needs[c2]:
                        count -= 1
        if min_len == float('inf'):
            return ''
        else:
            return s[start:start+min_len]

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        from collections  import defaultdict
        needs = defaultdict(int)
        for c in s1:
            needs[c] += 1
        window = defaultdict(int)
        left = 0
        right = 0
        count = 0
        while right < len(s2):
            c1 = s2[right]
            right += 1
            if c1 in needs:
                window[c1] += 1
                if window[c1] == needs[c1]:
                    count += 1
            while count == len(needs):
                if right - left == len(s1):
                    # 如果子串长度与s1相等则包含
                    return True
                c2 = s2[left]
                if c2 in needs:
                    window[c2] -= 1
                    if window[c2] < needs[c2]:
                        count -= 1
                left += 1
        return False

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        from collections import defaultdict
        needs = defaultdict(int)
        window = defaultdict(int)
        left = 0
        right = 0
        count = 0
        res = []
        for c in p:
            needs[c] += 1
        while right < len(s):
            c1 = s[right]
            if c1 in needs:
                window[c1] += 1
                if window[c1] == needs[c1]:
                    count += 1
            right += 1
            while count == len(needs):
                if right - left == len(p):
                    res.append(left)
                c2 = s[left]
                if c2 in needs:
                    window[c2] -= 1
                    if window[c2] < needs[c2]:
                        count -= 1
                left += 1
        return res

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_len = 0
        left = 0
        right = 0
        n = len(s)
        from collections import defaultdict
        window = defaultdict(int)
        while right < n:
            c1 = s[right]
            right += 1
            window[c1] += 1
            while window[c1] > 1:
                c2 = s[left]
                left += 1
                window[c2] -= 1
            max_len = max(max_len, right - left)
        return max_len