LeetCode LCR 017. 最小覆盖子串

约 12 分钟
文章信息 5 个分类 4 个标签
分类
LeetCode 困难 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
字符串 哈希表 LCR 滑动窗口
目录

题目描述

✅ LCR 017. 最小覆盖子串

题意分析

在 s 中找一段连续的子串，使它「覆盖」t，并且长度最短；若不存在这样的子串就返回空字符串。答案要的是子串本身，所以除了长度还得记住起点。

「覆盖」的判定标准是按重数而不是按种类：t 中某个字符出现 k 次，窗口里就必须出现至少 k 次，多出来不要紧。这是本题最容易读错的一处——t = "AABC" 时只含一个 A 的窗口不算覆盖。

「连续」意味着答案对应原串上的一个区间 [left, right]，可以用两个下标刻画，而不必枚举字符组合。更重要的是覆盖性对区间单调：若 [left, right] 已经覆盖 t，那么把右端点继续往右扩张仍然覆盖；反之若当前区间没覆盖，缩短它只会更差。这条单调性说明左右端点都只需要单向移动。

另一个可以利用的信号是字符集有限：题面给的是英文字母大小写，全部落在 ASCII 范围内，因此计数容器可以用一个固定长度的数组，判断是否覆盖不需要遍历哈希表。

边界情形：t 比 s 长时必然返回空串；s 中根本没有某个必需字符时返回空串；答案可能就是整个 s（如 s = "ab"、t = "ba"），所以最优长度的初值必须比 s 的长度还大；s 与 t 都只有一个字符且相等时答案是长度 1 的窗口，收缩逻辑不能把长度 1 的窗口排除掉。

解法：滑动窗口维护字符欠账

核心思路

暴力做法枚举所有 $O( s ^2)$ 个子串，每个再花 $O( s + t )$ 判断是否覆盖，总代价 $O( s ^3)$。瓶颈很清楚：相邻的两个候选区间只差一个字符，判覆盖却每次都从零重算。

于是改成增量维护。核心是两个量：数组 need[ch] 表示窗口还欠多少个字符 ch，整数 missing 表示窗口一共还欠多少个字符。初始化时 need 就是 t 的频次表，missing = t.length()。字符入窗时 need[ch]--，出窗时 need[ch]++，所以 need[ch] 允许是负数，负值表示窗口里这个字符多余了几个。

关键在于 missing 的更新只在「欠账真的发生变化」时才动。入窗时先看 need[ch] > 0 是否成立：成立说明这个字符本来还欠着，这次入窗填上了一格真实缺口，missing--；不成立说明窗口里这个字符已经够用（甚至过剩），这次入窗只是让它更过剩，missing 不动。出窗时对称：先 need[ch]++，若增后 need[ch] > 0，说明刚移出的那一个是必需的，窗口从此欠账，missing++；若增后仍 ≤ 0，移走的只是多余副本，窗口依然覆盖。

由此得到循环不变量：missing 恒等于 need 中所有正值之和，也就是当前窗口与覆盖 t 之间的真实差距。所以 missing == 0 就是「窗口覆盖 t」的充要条件，判定是 $O(1)$ 的，不必扫描整张计数表。

有了 $O(1)$ 判定，算法形状就是标准的可变窗口：右端点逐个右移扩张，一旦 missing == 0 就进入内层循环，先记录当前窗口长度，再从左端移出字符尝试继续缩短，直到窗口重新欠账为止。内层用 while 而不是 if 很关键——missing 归零的那一刻，左边可能积压了一串多余字符，必须一路挤干净，否则记录到的不是以当前 right 结尾的最短合法窗口。

正确性论证：对每个右端点 right，内层循环退出前的最后一次记录，恰好对应「使 [left, right] 覆盖 t 的最大 left」，即以 right 结尾的最短合法窗口。所有右端点的最短窗口取最小值，就是全局答案；而任何合法窗口都有唯一的右端点，不会被漏掉。

左右端点都只增不减：right 由外层循环推进，left 只在内层循环里 ++，两者的总位移都不超过 |s|，这就是线性复杂度的来源。

解题步骤

  • 建欠账表：开一个长度 128 的 need 数组，遍历 t 把每个字符的需求数加进去。用固定数组而不是哈希表，是为了让入窗、出窗和判覆盖都是纯数组下标操作。
  • 初始化状态：missing = t.length()，因为初始窗口为空，欠的正好是 t 的全部字符（含重复）；left = 0；bestLen 取一个不可能达到的大值（Java 用 Integer.MAX_VALUE，Go 用 len(s) + 1），bestStart = 0。bestLen 的初值必须严格大于 |s|，否则整串就是答案时会被漏掉。
  • 右端点扩张：right 从 0 扫到末尾，取 in = s[right]。先判断 need[in] > 0 再执行 need[in]--，顺序颠倒就会把「填补缺口」误判成「制造过剩」。
  • 判覆盖并收缩：while (missing == 0) 时，先用 right - left + 1 尝试更新 bestLen 和 bestStart——此刻窗口一定是合法的，是唯一能安全记录答案的时机。
  • 移出左端字符：取 out = s[left]，执行 need[out]++；若增后 need[out] > 0，说明移走的是必需字符，missing++ 让内层循环退出。最后 left++。这一步的 need[out]++ 绝不能省，否则 missing 永远为 0，内层循环出不来。
  • 收尾：外层结束后若 bestLen 仍是初值，说明从未出现合法窗口，返回空字符串；否则返回 [bestStart, bestStart + bestLen) 这一段子串。

以 s = "ADOBECODEBANC"、t = "ABC" 走一遍。初始 need[A] = need[B] = need[C] = 1，missing = 3，left = 0。

右端点推进到下标 0 的 A，need[A] 由 1 变 0，missing = 2；下标 1 的 D、下标 2 的 O 都不是必需字符，need 变成 -1，missing 保持 2；下标 3 的 B 使 missing = 1；下标 4 的 E 无影响；下标 5 的 C 使 missing = 0。此时窗口是 [0, 5] 即 "ADOBEC"，长度 6，记为当前最优。开始收缩：移出下标 0 的 A，need[A] 回到 1，为正，missing = 1，left = 1，内层退出。

继续推进：下标 9 的 B 入窗时 need[B] 已经是 0（下标 3 的 B 还在窗口里），所以 missing 不变、need[B] 变 -1；下标 10 的 A 入窗使 missing = 0。窗口 [1, 10] 长度 10，不优于 6。收缩阶段依次移出 D、O、下标 3 的 B（need[B] 由 -1 变 0，不为正，窗口仍合法）、E，left 走到 5，窗口 [5, 10] 长度 6，与最优并列不更新；再移出下标 5 的 C，need[C] 变 1 为正，missing = 1，left = 6，退出。

最后推进到下标 12 的 C，missing 再次归零。收缩阶段：移出下标 6 的 O（need[O] 由 -1 变 0），left = 7，窗口长度 6；移出下标 7 的 D，left = 8，窗口 [8, 12] 长度 5，更新最优；移出下标 8 的 E（need[E] 由 -1 变 0，仍合法），left = 9，窗口 [9, 12] 长度 4，更新最优为 bestStart = 9、bestLen = 4；再移出下标 9 的 B，need[B] 变 1 为正，missing = 1，left = 10，退出。外层结束，返回 s[9..12] 即 "BANC"。

再看 s = "a"、t = "aa"：missing 初值为 2，唯一一次入窗只能把它降到 1，while 从未进入，bestLen 保持初值，返回 ""。

代码实现

class Solution {
    public String minWindow(String s, String t) {
        int[] need = new int[128];
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }

        int missing = t.length();
        int left = 0;
        int bestStart = 0;
        int bestLen = Integer.MAX_VALUE;

        for (int right = 0; right < s.length(); right++) {
            char in = s.charAt(right);
            if (need[in] > 0) {
                missing--;
            }
            need[in]--;

            // missing 为 0 时窗口已覆盖 t，开始尽量左收缩。
            while (missing == 0) {
                int len = right - left + 1;
                if (len < bestLen) {
                    bestLen = len;
                    bestStart = left;
                }

                char out = s.charAt(left);
                need[out]++;
                if (need[out] > 0) {
                    missing++;
                }
                left++;
            }
        }

        if (bestLen == Integer.MAX_VALUE) {
            return "";
        }
        return s.substring(bestStart, bestStart + bestLen);
    }
}

func minWindow(s string, t string) string {
    need := make([]int, 128)
    for i := 0; i < len(t); i++ {
        need[t[i]]++
    }

    missing := len(t)
    left := 0
    bestStart := 0
    bestLen := len(s) + 1

    for right := 0; right < len(s); right++ {
        in := s[right]
        if need[in] > 0 {
            missing--
        }
        need[in]--

        // missing 为 0 时窗口已覆盖 t，开始尽量左收缩。
        for missing == 0 {
            length := right - left + 1
            if length < bestLen {
                bestLen = length
                bestStart = left
            }

            out := s[left]
            need[out]++
            if need[out] > 0 {
                missing++
            }
            left++
        }
    }

    if bestLen == len(s)+1 {
        return ""
    }
    return s[bestStart : bestStart+bestLen]
}

复杂度分析

  • 时间复杂度：$O( s + t )$。建欠账表扫 t 一遍是 $O( t )$；主循环中 right 走 |s| 步，内层 while 每次执行都让 left 前进一格，而 left 单调不减、总位移不超过 |s|，因此内层循环的总次数摊还后是 $O( s )$ 而非每轮 $O( s )$；每步只做常数次数组读写，missing == 0 的判覆盖也是 $O(1)$，不含隐藏的字符集遍历。主导项是 |s|。
  • 空间复杂度：$O(C)$，其中 C = 128 是 ASCII 字符集大小，need 数组的规模与输入长度无关，可视为常数；其余只有若干下标与计数变量，返回值不计入额外空间。

关键点总结

  • 把「是否满足约束」压缩成一个 $O(1)$ 可查的标量（这里是 missing），是所有可变窗口题的通用手法；一旦判定要遍历计数表，复杂度就会多乘一个字符集大小。
  • 计数值允许为负是这套写法的精髓：负值携带了「过剩多少」的信息，正是它让出窗时能区分「移走了必需字符」与「移走了多余副本」。
  • 「先判断再修改」与「先修改再判断」的次序，取决于修改的方向：入窗前 need 的正负才代表旧的欠账，出窗后 need 的正负才代表新的欠账，两处顺序天然相反，不能凭手感统一。
  • 内层收缩必须是 while 而不是 if：missing 归零的时刻左侧可能积压多个无用字符，只挤一格就无法保证得到以当前右端点结尾的最短窗口。
  • 求最短区间时，最优长度的初值要取一个不可达的上界（|s| + 1 或整型最大值），并用它兼作「无解」的标记，能省掉一个布尔变量。
  • 面试视角：先点明「按重数覆盖」和「原串连续」这两个读题结论，再讲清 missing 的不变量以及为什么左右指针单向移动就够，这两点讲透了这道困难题就稳了。常见追问有三个：need 为什么允许负数、内层为什么用 while、以及若把「子串」改成「子序列」会怎样——后者顺序有额外约束，窗口法不再成立，需要转成区间型动态规划。用双层循环枚举子串再逐个判覆盖不能当主答案，即使用哈希表加速判定也只是把 $O( s ^3)$ 降到 $O( s ^2)$。

易错点总结

  • 入窗时先做 need[in]-- 再判断 need[in] > 0：填补最后一个缺口时计数已经被减成 0，判断失败、missing 不减。用 s = "a"、t = "a" 测试，missing 永远是 1，while 不会进入，返回 "" 而正确答案是 "a"。
  • 入窗判断写成 need[in] >= 0，把「计数恰好相等、已经够用」也当成填补缺口：重复字符入窗会重复扣减 missing，窗口尚未覆盖 t 就被判定合法而提前收缩。用 s = "AAB"、t = "AB" 测试，第二个 A 入窗时 need[A] = 0 也触发 missing--，missing 提前归零，"AA" 乃至 "A" 被当成合法窗口记录，最终返回 "A"，正确答案是 "AB"。
  • 内层收缩用 if 代替 while：每个右端点只挤掉一格左侧字符。用 s = "AAB"、t = "AB" 测试，missing 在下标 2 归零时记下长度 3 的 "AAB"，随后只移出一个 A 就退出，最终返回 "AAB"，而正确答案是 "AB"。
  • 忘记 need[out]++，只写 left++：missing 再也不会变回正数，while (missing == 0) 成为死循环，left 冲出字符串范围，s.charAt(left) 抛 StringIndexOutOfBoundsException（Go 中是切片下标 panic）。
  • 把更新答案的代码挪到 left++ 之后：记录的是已经收缩过头、不再覆盖 t 的窗口。用 s = "a"、t = "a" 测试，记下的长度是 0 - 1 + 1 = 0，bestLen 变成 0，最终返回 ""。
  • bestLen 初值取 s.length()：整个 s 恰好是唯一答案时长度不小于初值、不会被记录。用 s = "ab"、t = "ba" 测试会返回 ""，正确答案是 "ab"。
  • 只统计字符种类、不看出现次数：用 s = "ABC"、t = "AABC" 测试会返回 "ABC"，但 s 里只有一个 A，正确答案是 ""。
  • 计数数组开成 new int[26] 并用 ch - 'a' 索引：题面的 t = "ABC" 是大写字母，'A' - 'a' 等于 -32，直接抛出数组越界异常。字符集含大小写时必须用 128 长度的表或哈希表。
  • 收缩条件写成 while (missing == 0 && left < right)：多加的条件把长度为 1 的窗口排除在外。用 s = "a"、t = "a" 测试，left < right 为假，答案从未被记录，返回 ""。
  • 返回时写成 s.substring(bestStart, bestLen)：把长度当成了结束下标。用 s = "ADOBECODEBANC"、t = "ABC" 测试，bestStart = 9、bestLen = 4，substring(9, 4) 因为起点大于终点而抛出异常。

相似题目

题目 难度 考察点
面试题 17.18. 最短超串 中等 对象是整数数组且待覆盖元素互不重复，返回下标区间而非子串
3. 无重复字符的最长子串 中等 求最长而非最短，约束是「窗口内不重复」，扩张与收缩的触发条件正好相反
209. 长度最小的子数组 中等 同样求最短窗口，但合法性判据是数值和 ≥ target，只需一个前缀和变量
438. 找到字符串中所有字母异位词 中等 窗口长度固定为模式串长度，要求恰好相等而非覆盖，收缩退化为定长滑动
567. 字符串的排列 中等 定长窗口的判定版，只需返回是否存在，找到一个即可提前退出
30. 串联所有单词的子串 困难 覆盖单位从字符变成等长单词，需要按单词长度分组做多条独立的滑动窗口
424. 替换后的最长重复字符 中等 合法条件变成「窗口长度减最高频次 ≤ k」，需要额外维护窗口内的众数频次
1004. 最大连续1的个数 III 中等 只对 0 计数，欠账表退化成一个整数，是本题写法的最简特例
727. 最小窗口子序列 困难 要求 t 按顺序作为子序列出现，覆盖性不再对区间单调，滑动窗口整体失效