滑动窗口解题模板

题目要求

类型 1： 给定两个字符串 s 和 t，找满足某种变化规律的字串/最大字串/最大字串长度等。

类型 2：给定字符串 s，查找满足某种条件的最大/最小窗口。

解题模板

class Solution:
    def slidingWindowTemplate(s, t):
        # 定义其他变量，存储结果，存储判断条件等变量
        begin = end = 0

        while f(): # case 1: slide end
            # do something
            end += 1
            while g(): # case 2: slide begin
                # do something
                begin += 1
                # meet some condition

模版变形：

• 前后指针同步移动可以简化为一层循环
• exactly(K) = atMost(K) - atMost(K-1)

案例应用

案例 1： Leetcode 424

Medium: Longest Repeating Character Replacement

给定一个字符串 s 和整数 k，求 s 变换 k 次后得到的最长重复子串是多长。其中变换规律是：每次操作可以将一个字符变化成任意字符。重复字符串是指所有字符都相同的字符串。

end 每次滑动要做啥：

累计 s[end] 出现的次数。如果 s[end] 出现次数大于了窗口中最大重复次数，则更新最大重复次数。如果窗口长度大于 k + max_count 则需要移动 begin 指针。

begin 指针移动要做啥：

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        if not s:
            return 0
        begin = end = 0
        map = collections.defaultdict(int)
        max_count = max_len = 0

        while end < len(s):
            c = s[end]
            map[c] += 1
            max_count = max(max_count, map[c])

            end += 1

            while end - begin > k + max_count:
                b = s[begin]
                map[b] -= 1
                begin += 1

            max_len = max(max_len, end - begin)

        return max_len

案例 2：Max Consecutive Ones III

Medium: https://leetcode.com/problems/max-consecutive-ones-iii/solution/

给定一个只有 0 和 1 的数组 A 和一个操作次数 K，每次操作可以从 0 变成 1，求在 k 次操作下最大子数组的长度。

class Solution:
    def longestOnes(self, A: List[int], k: int) -> int:
        begin = end = 0
        max_len = 0
        nums_one = 0

        while end < len(A):
            if A[end] == 1:
                nums_one += 1

            end += 1
            while end - begin > nums_one + k:
                if A[begin] == 1:
                    nums_one -= 1
                begin += 1

            max_len = max(max_len, end - begin)

        return max_len

案例 3：Grumpy Bookstore Owner

Medium: https://leetcode.com/problems/grumpy-bookstore-owner/

class Solution:
    def maxSatisfied(self, cus: List[int], gru: List[int], x: int) -> int:
        init_sum = max_sum = 0
        n = len(cus)
        for i in range(n):
            if gru[i] == 0:
                init_sum += cus[i]

        begin = end = 0

        while end < n:
            if gru[end] == 1:
                init_sum += cus[end]
            # [begin, end]
            while end - begin == x:
                if gru[begin] == 1:
                    init_sum -= cus[begin]
                begin += 1

            max_sum = max(max_sum, init_sum)
            end += 1 # 考虑清楚下次 end 移动之前要做哪些事情

        return max_sum

案例 4： Longest Substring Without Repeating Characters

Medium: https://leetcode.com/problems/longest-substring-without-repeating-characters/

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        map = collections.defaultdict(int)
        counter = 0
        begin = end = 0

        max_len = 0

        while end < len(s):
            e = s[end]
            map[e] += 1
            if map[e] > 1: # e is repeating
                counter += 1 # counter is number of repeating

            end += 1

            while counter > 0: # has repeated number
                b = s[begin]
                if map[b] > 1:
                    counter -= 1
                map[b] -= 1

                begin += 1

            max_len = max(max_len, end - begin)

        return max_len

案例 5： Get Equal Substrings Within Budget

Medium: https://leetcode.com/problems/get-equal-substrings-within-budget/

class Solution:
    def equalSubstring(self, s: str, t: str, cost: int) -> int:
        begin = end = 0
        max_len = 0

        while end < len(s):
            cost -= abs(ord(s[end]) - ord(t[end]))
            end += 1

            while cost < 0:
                cost += abs(ord(s[begin]) - ord(t[begin]))
                begin += 1

            max_len = max(end - begin, max_len)

        return max_len

案例 6：Permutation in String

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

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        d = collections.Counter(s1)
        counter = len(d)

        begin = end = 0

        while end < len(s2):
            e = s2[end]
            if e in d:
                d[e] -= 1
                if d[e] == 0:
                    counter -= 1
            end += 1

            while counter == 0:
                b = s2[begin]
                if b in d:
                    d[b] += 1
                    if d[b] > 0:
                        counter += 1
                if end - begin == len(s1):
                    return True

                begin += 1

        return False

案例 7： Minimum Window Substring

https://leetcode.com/problems/minimum-window-substring/

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        map = collections.Counter(t)

        found = False
        begin = end = 0
        counter = len(map)
        start = 0
        min_len = len(s)

        while end < len(s):
            e = s[end]
            if e in map:
                map[e] -= 1
                if map[e] == 0:
                    counter -= 1
            end += 1

            while counter == 0:
                found = True
                b = s[begin]
                if b in map:
                    map[b] += 1
                    if map[b] > 0:
                        counter += 1

                if end - begin < min_len:
                    min_len = end - begin
                    start = begin

                begin += 1

        return s[start: start + min_len] if found else ""