最小覆盖子串 图解题解

这道题真正在问什么

给两个字符串 s 和 t，在 s 中找出最短的连续子串，使它包含 t 的全部字符——注意是「包含」而非「等于」，窗口里允许夹杂无关字符；且 t 里的重复字符要按次数算，t = "AAB" 就必须凑够两个 A。比如 s = "ADOBECODEBANC"、t = "ABC"，答案是 "BANC"。找不到时返回空串。

为什么暴力枚举子串行不通

最直觉的做法是枚举所有子串、逐个检查是否覆盖 t：起点终点组合有 O(n²) 个，每次检查还要 O(n) 扫一遍统计字符，加起来 O(n³)，s 稍长就完全跑不动。

破局的观察有两条。第一，覆盖性有单调性：一个窗口若已覆盖 t，再往右扩只会多不会少，检查更长的窗口毫无意义——该做的是收缩，看它还能多短。第二，窗口每次只在两端进出一个字符，覆盖状态完全可以增量维护，不必每次从头重数。这两条合起来，就把问题逼向了「双指针一趟扫完」的滑动窗口（也叫双指针窗口）。

怎么高效判断窗口已覆盖 t

先用计数表 need 记下 t 中每个字符需要的个数，再用 win 记录当前窗口内各字符的实际个数。判断覆盖不必逐项对比整张表：额外维护一个变量 formed，表示「已经凑够次数的字符种数」，当 formed 等于 t 中不同字符的总种数 required 时，窗口即完成覆盖。

formed 的维护是增量的：右端吃进字符 c 后，若 win[c] 恰好追平 need[c]，formed 加一；左端挤出字符后，若该字符的计数跌破需求，formed 减一。每次进出只花 O(1)，这正是整个算法能保持线性的关键一环。

为什么覆盖后必须立刻收缩左边界

算法的节奏是「右扩补齐、左缩压短」交替：右指针一路吃字符，直到 formed == required；随即进入收缩循环，每一步先用当前窗口长度 r - l + 1 更新最优答案，再把 s[l] 挤出窗口、l 右移，直到覆盖被破坏，然后回到右扩。

这样做不漏最优解的理由是：对每一个可能的右端点 r，收缩过程恰好找到了以 r 结尾的最短覆盖窗口——继续缩就不覆盖了，说明已经缩到底。所有右端点各自的最短窗口都被比较过，全局最短自然在其中。另外「先记录再移动 l」的顺序不能反，先移再记会把当前这个合法窗口漏掉。

复杂度怎么算，哪些细节容易错

时间 O(n)：右指针扫一遍 s，左指针也只向右、累计最多走 n 步，每步的计数增减都是 O(1)；空间 O(k)，两张计数表最多存 t 中不同字符数个键。

两个高频翻车点：一是只比字符种类、不比出现次数——t 里的重复字符必须按 need[c] 的计数凑够，只用集合判断会把 "AAB" 当成只要一个 A；二是拿到第一个覆盖窗口就直接返回——第一个只是「最早」不是「最短」，必须让窗口继续滑到 s 末尾，把每个右端点的收缩结果都比完才能收工。

Python

from collections import Counter
def minWindow(s, t):
    need = Counter(t)
    required = len(need)
    win = {}
    formed = 0
    l = 0; best = (float("inf"), 0, 0)
    for r, c in enumerate(s):
        win[c] = win.get(c, 0) + 1
        if c in need and win[c] == need[c]:
            formed += 1
        while l <= r and formed == required:
            if r - l + 1 < best[0]:
                best = (r - l + 1, l, r)
            win[s[l]] -= 1
            if s[l] in need and win[s[l]] < need[s[l]]:
                formed -= 1
            l += 1
    return "" if best[0] == float("inf") else s[best[1]:best[2]+1]

C++

string minWindow(string s, string t){
    unordered_map<char,int> need, win;
    for(char c : t) need[c]++;
    int required = need.size(), formed = 0, l = 0;
    int bestLen = INT_MAX, bl = 0;
    for(int r = 0; r < (int)s.size(); r++){
        char c = s[r]; win[c]++;
        if(need.count(c) && win[c] == need[c]) formed++;
        while(l <= r && formed == required){
            if(r - l + 1 < bestLen){ bestLen = r - l + 1; bl = l; }
            char d = s[l]; win[d]--;
            if(need.count(d) && win[d] < need[d]) formed--;
            l++;
        }
    }
    return bestLen == INT_MAX ? "" : s.substr(bl, bestLen);
}

Java

public String minWindow(String s, String t){
    int[] need = new int[128], win = new int[128];
    int required = 0;
    for(char c : t.toCharArray()){ if(need[c]++ == 0) required++; }
    int formed = 0, l = 0, bestLen = Integer.MAX_VALUE, bl = 0;
    for(int r = 0; r < s.length(); r++){
        char c = s.charAt(r); win[c]++;
        if(need[c] > 0 && win[c] == need[c]) formed++;
        while(l <= r && formed == required){
            if(r - l + 1 < bestLen){ bestLen = r - l + 1; bl = l; }
            char d = s.charAt(l); win[d]--;
            if(need[d] > 0 && win[d] < need[d]) formed--;
            l++;
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bl, bl + bestLen);
}