Sliding Window

滑动窗口的核心在于hua（~~划水的hua~~）。滑动窗口有点类似动态规划，在一些区间内找到最优解，而且也有一点双指针的思想。滑动窗口可以用以解决数组/字符串的子元素问题，它可以将嵌套的循环问题，转换为单循环问题，降低时间复杂度。可以把比较常见的暴力解法$O(n^2)$降到$O(n)$。其实如果提升算法效率就大概率会牺牲空间，提升空间大概率牺牲时间。大部分情况两者不能兼得。leetcode有很多关于滑动窗口比较有趣的问题。

76. Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string “”.

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

1
2
3

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

大致意思就是找到一个包含t的最小的子序列。这个问题可以使用最简单的暴力解法，双重循环就能解决，但是时间复杂度太高，这时候我们就可以通过滑动窗口来解决。滑动窗口一半是有左右两个指针来进行控制窗口的大小。右侧指针负责扩大窗口，左侧指针负责缩小窗口。右侧指针负责寻找到包含t的子序列，左侧指针负责对该子序列不断进行缩小直到找到最小包含t的子序列。

核心可以分成三部，如图所示。在第一步立马，R（右侧指针）先找到了满足需求的子序列，这时候L（左侧指针）开始减小窗口以便找到最小的子序列，当L指向D的时候该子序列不满足要求，然后R开始继续向右边移动来找到满足条件的子序列。当R指向A的时候，该子序列满足要求，然后L向右移动来缩小窗口大小。然后重复该步骤，直到找到最小的子序列。

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(s) < len(t):
            return ""

        target = {}
        windows = {}
        end = len(s)
        start = -1

        left = 0
        right = 0

        tValid = 0

        for val in t:
            target[val] = target.get(val, 0) + 1


        while right < len(s):
            c = s[right]

            if c not in target:
                right += 1
                continue

            windows[c] = windows.get(c, 0) + 1
            if windows[c] == target[c]:
                tValid += 1

            # then left start to move
            while tValid == len(target):
                lc = s[left]
                if lc not in target:
                    left += 1
                    continue
                # remove the element from the window
                windows[lc] -= 1
                if windows[lc] < target[lc]:
                    tValid -= 1

                    if right - left < end:
                        end = right - left + 1
                        start = left
                left += 1

            right += 1

        if start == -1:
            return ""
        return s[start:start + end]