#76

困难

中频

滑动窗口

最小覆盖子串

这是一道围绕字符串展开的高频练习。建议先掌握「滑动窗口」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

字符串

原题练习

题目分析

给你两个字符串 s 和 t。

要求你在 s 里找出一段最短的连续子串，使得这段子串能够覆盖 t 里的所有字符，并且每个字符出现的次数也要够。

如果不存在这样的子串，就返回空字符串。

一句话概括：

在主串里找到一段最短窗口，让它完整覆盖目标串需要的所有字符。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：用滑动窗口覆盖目标字符计数，窗口满足要求后尽量收缩左边界，持续更新最短答案。

推荐代码

推荐解法：滑动窗口

时间复杂度： O(m+n)

空间复杂度： O(n)

核心思路：用滑动窗口覆盖目标字符计数，窗口满足要求后尽量收缩左边界，持续更新最短答案。

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }

        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();

        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0;
        int valid = 0;
        int start = 0;
        int minLen = Integer.MAX_VALUE;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).intValue() == need.get(c).intValue()) {
                    valid++;
                }
            }

            while (valid == need.size()) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    start = left;
                }

                char d = s.charAt(left);
                left++;
                if (need.containsKey(d)) {
                    if (window.get(d).intValue() == need.get(d).intValue()) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

结构化讲解

面试时怎么讲

开场思路

这题我会用滑动窗口，核心是维护窗口是否已经覆盖了目标字符串的所有需求。

核心过程

先统计 t 中每个字符的需求次数。
右指针不断扩张窗口，把字符纳入统计。
一旦窗口满足所有需求，就记录答案并尝试左缩，寻找更短覆盖。
左缩导致窗口失去合法性后，再继续右扩，如此往复直到扫描结束。

复杂度总结

时间复杂度 O(m+n)，空间复杂度 O(n)。

面试补一句：这题最核心的不变量是“窗口何时刚好满足需求”。

核心思路

最小覆盖子串的难点不是扩窗口，而是知道“什么时候窗口已经够了”以及“够了以后如何安全收缩”。核心是用哈希表维护目标字符缺口。

步骤讲解

先统计目标字符串所需字符

用哈希表记录 t 中每个字符需要出现多少次，并维护一个待满足字符种类数。

为什么这样做：只有知道缺什么、缺多少，窗口才知道什么时候算合法。

对应代码提示：Map<Character, Integer> need = new HashMap<>();

右指针扩张窗口补齐字符

不断把右侧字符纳入窗口，并更新窗口计数；当某个字符刚好满足需求时，减少待满足计数。

为什么这样做：右扩负责先让窗口从不合法走向合法。

对应代码提示：window.put(c, window.getOrDefault(c, 0) + 1);

窗口合法后尽量收缩左边界

当窗口已经覆盖 t，就尝试移动左指针，更新最短答案，同时维持合法性判断。

为什么这样做：题目要的是最短覆盖子串，所以每次合法都要主动缩到不能再缩。

对应代码提示：while (valid == need.size()) { ... }

易错点

只比较字符是否出现，没比较次数

像 AABC 覆盖 ABC 可以，但覆盖 AABC 就不够。

正确理解：窗口必须维护计数，而不是只维护是否存在。

窗口合法后没立刻收缩

这样会错过更短的可行答案。

正确理解：一旦满足需求，就进入内层 while 尽量左缩。

左缩时没同步更新合法状态

删除关键字符后，窗口可能已经不再覆盖目标。

正确理解：左边界移出字符时，要同步更新计数和 valid。

复杂度与适用判断

时间复杂度：O(m+n)

空间复杂度：O(n)

比其他方案更好在哪里：比暴力枚举所有子串后检查频次高效得多，复杂度从平方级降到线性级。

适用判断：当题目是“最短/最长连续区间，且区间要满足某种频次约束”时，优先想到滑动窗口。

额外提醒

窗口合法时要马上缩，这一步决定答案是否最短。