2.4 滑动窗口

76. 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)$。

C++

string minWindow(string s, string t) {
    vector<bool> valid(128, false);
    vector<int> freq(128, 0);
    // 统计t中的字符情况。
    for (int i = 0; i < t.length(); ++i) {
        valid[t[i]] = true;
        ++freq[t[i]];
    }
    // 移动滑动窗口，不断更改统计数据。
    int count = 0;
    int min_l = -1, min_length = -1;
    for (int l = 0, r = 0; r < s.length(); ++r) {
        if (!valid[s[r]]) {
            continue;
        }
        // 把r位置的字符加入频率统计，并检查是否补充了t中缺失的字符。
        if (--freq[s[r]] >= 0) {
            ++count;
        }
        // 滑动窗口已包含t中全部字符，尝试右移l，在不影响结果的情况下寻找最短串。
        while (count == t.length()) {
            if (min_length == -1 || r - l + 1 < min_length) {
                min_l = l;
                min_length = r - l + 1;
            }
            // 把l位置的字符移除频率统计，并检查t中对应字符是否重新缺失。
            if (valid[s[l]] && ++freq[s[l]] > 0) {
                --count;
            }
            ++l;
        }
    }
    return min_length == -1 ? "" : s.substr(min_l, min_length);
}

Python

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]