最小覆盖子串 | 每日算法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。

示例 1

输入：s = "ADOBECODEBANC", t = "ABC"

输出："BANC"

💭 模拟答题者思考

1. 暴力：枚举所有子串检查是否覆盖 t。要滑动窗口就必须回答「可行」（cover）→「比长度」。

2. 右指针 r 扩张到覆盖为止，一旦覆盖就尝试收左指针 l 缩到最短。

3. 需要 O(1) 判断是否覆盖，所以引入计数表 need/window 和 valid 计数。

4. 当 valid == distinct_chars_in_t 时，当前窗口 [l,r) 是一个可行解，尝试缩小 l 找更短。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`need[c]`	map<char,int>	定义：目标串 t 对字符 c 的需求次数维护：不变量，初始化为 t 的字符频率更新：不更新
`window[c]`	map<char,int>	定义：当前窗口内字符 c 的计数维护：随窗口滑动实时反映窗口内容更新：窗口右扩时 window[c]++，左缩时 window[c]--
`valid`	int	定义：已满足需求的字符种类数维护：每轮后 valid = 满足 window[c] >= need[c] 的字符 c 的数量更新：当 window[c] 刚好等于 need[c]（从 < 变成 =）时 valid++

⌨️ 落码步骤

1. 统计 need：遍历 t，对每个字符 need[c]++

2. 右指针 r 扩张：window[s[r]]++，若 window[s[r]] == need[s[r]] 则 valid++

3. 当 valid == len(need)（全部满足），循环收缩左指针：更新答案，window[s[l]]--，若 window[s[l]] < need[s[l]] 则 valid--，l++

4. 返回最短子串或空串

💻 代码实现

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = Counter(t)
        need_types = len(need)
        window = Counter()
        valid = 0
        l = 0
        start, min_len = 0, float('inf')

        for r in range(len(s)):
            c = s[r]
            window[c] += 1
            if window[c] == need[c]:
                valid += 1

            while valid == need_types:
                if r - l + 1 < min_len:
                    start, min_len = l, r - l + 1

                d = s[l]
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1
                l += 1

        return s[start:start+min_len] if min_len != float('inf') else ''

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map need, window;
        for (char c : t) need[c]++;

        int valid = 0;
        int l = 0, start = 0, min_len = INT_MAX;

        for (int r = 0; r < s.size(); r++) {
            char c = s[r];
            window[c]++;
            if (need.count(c) && window[c] == need[c])
                valid++;

            while (valid == need.size()) {
                if (r - l + 1 < min_len) {
                    start = l;
                    min_len = r - l + 1;
                }
                char d = s[l];
                if (need.count(d) && window[d] == need[d])
                    valid--;
                window[d]--;
                l++;
            }
        }
        return min_len == INT_MAX ? "" : s.substr(start, min_len);
    }
};
// 时间 O(m+n)，空间 O(|Σ|)

📈 复杂度分析

时间复杂度 O(m+n)

空间复杂度 O(|Σ|)

⚠️ 常见坑

❗ valid 计数逻辑：必须 window[c] 刚好等于 need[c] 时才 valid++，超过不算（否则重复字符会虚增 valid）。

❗ 收缩时更新顺序：先判断 window[d]==need[d] 再 window[d]--，和扩张时顺序相同。

❗ 返回空串的判断：min_len 仍是 INF 说明从未形成合法窗口。

🔍 必测边界 Case

Case 1：s 和 t 相同

s = "ABC", t = "ABC" → 输出 "ABC"

Case 2：t 比 s 长

s = "A", t = "AB" → 输出 ""

Case 3：t 有重复字符

s = "AAB", t = "AA" → 输出 "AA"