LC76. 最小覆盖子串

题目描述

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串，我们保证它是唯一的答案。 示例 1： 输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 示例 2： 输入：s = "a", t = "a" 输出："a" 示例 3: 输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。 提示： 1 <= s.length, t.length <= 105 s 和 t 由英文字母组成 进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

题目解析

题目在说什么

简单来说，题目给了你两个字符串：一个长的 s，一个短的 t。你要在 s 中找出一个最短的连续片段，这个片段里必须包含 t 中所有的字符（包括重复的）。如果找不到，就返回空字符串。

举个例子：

• s = "ADOBECODEBANC"，t = "ABC"。

在 s 中，有很多片段包含 A、B、C，比如 "ADOBEC" 和 "BANC" 都包含 A、B、C。但 "BANC" 只有 4 个字符，比 "ADOBEC" 的 6 个字符短，所以答案是 "BANC"。

注意：如果 t = "aa"，那么你找的片段里必须至少有两个 'a'，不能只有一个。

思路是怎么来的

想象你有一张购物清单（t），上面写着需要买的东西：比如 "ABC" 就是需要 1 个 A、1 个 B、1 个 C。 现在你走进一个长长的货架（s），货架上摆满了字母。你想找一个最短的连续货架区域，里面正好包含清单上的所有东西。

一个笨办法：从每个位置开始，往右看，直到找到包含所有需要东西的区域。这样会非常慢，因为要检查很多次。

聪明的办法：用两个指针（左指针和右指针）画出一个“窗口”，就像用手在货架上比划一个区域。 1. 先让右指针往右走，扩大窗口，直到窗口里包含了清单上的所有东西。 2. 然后尝试把左指针往右移，缩小窗口，看看能不能在仍然包含所有东西的情况下让窗口更短。 3. 一旦左指针移多了，导致窗口里缺了某个东西，就停止缩小，继续让右指针往右走，再找下一个符合条件的窗口。 4. 不断重复，记录下最短的那个窗口。

这个“滑动窗口”的思路就像你在货架上滑动一个框，不断调整框的大小，找到最小的框。

代码逐步拆解

我们来看参考代码，一步一步拆解。

1. 准备一个“需求表”

int[] map = new int[128];
for (int i = 0; i < t.length(); i++) {
    map[t.charAt(i)]++;
}

• map 是一个数组，长度 128，对应 ASCII 码表里的所有字符。
• 我们遍历 t，把每个字符对应的位置加 1。比如 t = "ABC"，那么 map['A'] 变成 1，map['B'] 变成 1，map['C'] 变成 1。
• 这个 map 就是我们的“购物清单”：正数表示还需要多少个该字符。

2. 初始化变量

int windowLength = s.length() + 1;  // 记录最短窗口长度，初始设为一个很大的数
int left = 0;                       // 左指针
int right = 0;                      // 右指针
int count = t.length();             // 还需要多少个字符才能满足条件
int start = 0;                      // 最短窗口的起始位置

• count 表示“还差几个字符没凑齐”。一开始 t 有 3 个字符，所以 count = 3。
• windowLength 初始设为一个很大的数（比 s 长度还大 1），方便后面比较。

3. 右指针向右移动，扩大窗口

while (right < s.length()) {
    char c = s.charAt(right);
    if (map[c] > 0) {
        count--;  // 这个字符是需要的，凑齐一个
    }
    map[c]--;     // 把这个字符从需求表中“消耗”掉

• 每次右指针指向一个字符 c。
• 如果 map[c] > 0，说明这个字符是清单上需要的，那么 count 减 1，表示我们凑齐了一个需要的东西。
• 不管是不是需要的，都要把 map[c] 减 1。这样，如果这个字符是多余的（比如清单上没有，或者已经够了），map[c] 就会变成负数，表示“多出来了”。

4. 当窗口包含所有需要字符时，尝试缩小左边界

    while (count == 0) {
        if (right - left + 1 < windowLength) {
            windowLength = right - left + 1;
            start = left;
        }
        char leftChar = s.charAt(left);
        if (map[leftChar] == 0) {
            count++;  // 这个字符是关键的，移除后就不够了
        }
        map[leftChar]++;  // 把这个字符“还回去”
        left++;           // 左指针右移
    }
    right++;  // 右指针继续右移
}

• 当 count == 0 时，说明当前窗口已经包含了 t 的所有字符。
• 先检查当前窗口长度是否比之前记录的最短长度更小，如果是，就更新 windowLength 和 start。