2.4 滑动窗口

# 2.4 滑动窗口

## [76. Minimum Window Substring](https://leetcode.com/problems/minimum-window-substring/)

### 题目描述

给定两个字符串 s 和 t，求 s 中包含 t 所有字符的最短连续子字符串的长度，同时要求时间复杂度不得超过 $O(n)$。

### 输入输出样例

输入是两个字符串 s 和 t，输出是一个 S 字符串的子串。如果不存在解，则输出一个空字符串。

```
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
```

在这个样例中，s 中同时包含一个 A、一个 B、一个 C 的最短子字符串是“BANC”。

### 题解

本题使用滑动窗口求解，即两个指针 l 和 r 都是从最左端向最右端移动，且 l 的位置一定在 r 的左边或重合。C++ 题解中使用了两个长度为 128 的数组，valid 和 freq，来映射字符（ASCII
只包含 128 个字符）。其中 valid 表示每个字符在 t 中是否存在，而 freq 表示目前 t 中每个字符在 s 的滑动窗口中缺少的数量：如果为正，则说明还缺少；如果为负，则说明有盈余。Python 题解
则直接使用 Counter 数据结构同时统计 t 中存在的字符和其缺少的数量（也可以用 dict 替代）。注意本题虽然在 for 循环里出现了一个 while 循环，但是因为 while 循环负责移动 l 指针，且 l 只会
从左到右移动一次，因此总时间复杂度仍然是 $O(n)$。

```py
def minWindow(s: str, t: str) -> str:
    # 统计t中的字符情况，等价于：
    # freq = dict()
    # for c in t:
    # freq[c] = freq.get(c, 0) + 1
    freq = Counter(t)
    # 移动滑动窗口，不断更改统计数据。
    count = 0
    min_l, min_length = None, None
    l = 0
    for r in range(len(s)):
        if s[r] not in freq:
            continue
        # 把r位置的字符加入频率统计，并检查是否补充了t中缺失的字符。
        freq[s[r]] -= 1
        if freq[s[r]] >= 0:
            count += 1
        # 滑动窗口已包含t中全部字符，尝试右移l，在不影响结果的情况下寻找最短串。
        while count == len(t):
            if min_length == None or r - l + 1 < min_length:
                min_l = l
                min_length = r - l + 1
            # 把l位置的字符移除频率统计，并检查t中对应字符是否重新缺失。
            if s[l] in freq:
                freq[s[l]] += 1
                if freq[s[l]] > 0:
                    count -= 1
            l += 1
    return "" if min_length is None else s[min_l: min_l + min_length]
```