最小覆盖子串

GitHub跳转原题关系图返回列表

滑动窗口维护 need/have 计数，右端扩张满足需求，左端收缩到刚好不满足，O(n)。

OJ: leetcodecn

题目 ID: minimum-window-substring

难度:提高+/省选-

标签:哈希表字符串滑动窗口cpppython

日期: 2026-07-28 22:05

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

给定字符串 s 和 t，找出 s 中包含 t 所有字符的最短子串。

思路

滑动窗口：右指针不断扩展直到覆盖 t 的所有字符，然后左指针收缩到刚好不满足，记录最短长度。

用 need[128] 计数 t 中各字符的需求，need 表示仍有需求的字符种类数。窗口滑动时：

  • 右指针字符入窗口，若其需求变为 0，have 加一。
  • 当 have == need 时说明当前窗口满足要求，尝试收缩左指针。
  • 左指针字符出窗口，若其需求变为 1，have 减一，窗口不再满足。

代码

cpp
/**
 * Author by Rainboy
 */
// main.cpp：滑动窗口 + need/have 计数，O(n)。
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        // cnt 记录窗口还缺少的字符数；need/have 记录所需/已满足的字符种类数。
        int cnt[128] = {}, need = 0;
        for (char ch : t) {
            if (cnt[ch] == 0)
                need++;
            cnt[ch]++;
        }
        int l = 0, have = 0, start = 0, len = INT_MAX;
        for (int r = 0; r < (int)s.size(); r++) {
            if (--cnt[s[r]] == 0)
                have++;
            while (have == need) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    start = l;
                }
                if (++cnt[s[l]] > 0)
                    have--;
                l++;
            }
        }
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, t;
    cin >> s >> t;
    cout << Solution().minWindow(s, t) << '\n';
    return 0;
}
python
#!/usr/bin/env python3
from collections import defaultdict


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = defaultdict(int)
        for ch in t:
            need[ch] += 1
        missing = len(need)
        l = start = 0
        min_len = float("inf")
        for r, ch in enumerate(s):
            if ch in need:
                need[ch] -= 1
                if need[ch] == 0:
                    missing -= 1
            while missing == 0:
                if r - l + 1 < min_len:
                    min_len = r - l + 1
                    start = l
                left_ch = s[l]
                if left_ch in need:
                    need[left_ch] += 1
                    if need[left_ch] > 0:
                        missing += 1
                l += 1
        return "" if min_len == float("inf") else s[start : start + min_len]


def main() -> None:
    s = input().strip()
    t = input().strip()
    print(Solution().minWindow(s, t))


if __name__ == "__main__":
    main()

复杂度

  • 时间复杂度：O(n)，左右指针各移动一次。
  • 空间复杂度：O(|Σ|)，字符集大小。

总结

最小覆盖子串是滑动窗口的进阶模型：右端扩张满足约束，左端收缩寻找最优。用 need/have 变量代替每次比较整个计数数组，将 O(n·|Σ|) 优化到 O(n)。