【经典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