好的，我们这次来详细讲解 LeetCode 第 11 题「盛最多水的容器」。

哦，等等，我注意到「盛最多水的容器」已经在你的“已讲过”列表里了。让我重新选择一个。

我们这次来详细讲解 LeetCode 第 42 题「接雨水」。

嗯？这个也在列表里。看来我需要更仔细地检查列表。

让我们避开列表中的题目。我选择 LeetCode 第 76 题「最小覆盖子串」。

这道题非常经典，结合了哈希表和滑动窗口两种重要思想，我们可以循序渐进地把它讲清楚。

LeetCode 第 76 题：最小覆盖子串

1. 题目描述

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

注意：

• 对于 t 中重复的字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果存在这样的子串，我们保证它是唯一答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3：

输入：s = "a", t = "aa"
输出：""
解释：t 中有两个 'a'，但 s 中只有一个 'a'，所以无法覆盖，返回空字符串。

2. 题意理解与核心思路分析

我们先来把题目要求拆解成更具体的条件：

1. 目标：在字符串 s 中找到一个连续的子串。
2. 条件：这个子串必须完全覆盖字符串 t 中的所有字符。
   • “覆盖”意味着：子串中，每种字符的数量都必须大于等于 t 中该字符的数量。
   • 例如，如果 t = "AAB"，那么有效的子串必须至少包含两个 ‘A’ 和一个 ‘B’。
3. 要求：在所有满足条件的子串中，我们要找长度最短的那个。

暴力解法会怎样？
最直接的想法是，枚举 s 的所有子串（起点 i 和终点 j），然后检查每个子串是否覆盖了 t。这需要 O(N²) 的枚举时间，加上检查子串的时间，总复杂度会达到 O(N³)，对于较长的字符串是完全不可接受的。

我们需要一个更高效的方法：滑动窗口

滑动窗口是处理这类“满足某种条件的最短/最长连续子串”问题的利器。其核心思想是：

• 用两个指针 left 和 right 来形成一个窗口 [left, right]，这个窗口代表 s 的一个子串。
• 开始时，left 和 right 都指向开头。
• 我们不断地移动 right 指针来扩大窗口，直到窗口中的子串包含了 t 的所有字符。
• 此时，我们移动 left 指针来收缩窗口，以找到能满足条件的最小窗口。
• 在收缩过程中，一旦窗口不再满足条件，我们就又继续移动 right 指针。如此反复，直到 right 指针到达 s 的末尾。

这个过程中，我们就像在移动一个大小可变的窗口，通过一伸一缩来遍历所有可能的候选子串。

3. 关键问题：如何判断窗口是否覆盖了 t？

我们需要一个高效的方法来比较窗口内的字符和 t 的字符。这里我们使用哈希表（或称为计数器）。

• need： 一个哈希表，用来记录 t 中每个字符需要的数量。
  • 例如 t = "AAB"，则 need: {'A': 2, 'B': 1}。
• window： 一个哈希表，用来记录当前窗口中，属于 t 的字符的当前数量。
  • 例如，当前窗口是 "ADOA"，那么对于 t="AAB"，window: {'A': 2, 'B': 0}。

那么，如何判断窗口“满足条件”呢？我们引入一个变量 valid 来记录当前窗口中已经满足 need 要求数量的字符种类数。

• 当 window 中某个字符的数量 等于 need 中该字符的数量时，我们就说这个字符的要求被满足了，valid 就加 1。
• 当 valid 的值 等于 need 中不同字符的种类数时，就说明整个窗口已经满足了覆盖 t 的条件。

举个例子：
t = "AAB"

• need = {'A': 2, 'B': 1}，need 的大小（不同字符的种类数）为 2。
• 初始状态：valid = 0。
• 假设窗口现在是 "AAB"：
  • window[‘A’] = 2，等于 need[‘A’] = 2，所以字符 ‘A’ 的要求被满足，valid 变为 1。
  • window[‘B’] = 1，等于 need[‘B’] = 1，所以字符 ‘B’ 的要求被满足，valid 变为 2。
• 此时 valid (2) == need.size (2)，说明窗口满足条件。

4. 算法步骤详解（一步步演示）

我们以示例 s = "ADOBECODEBANC", t = "ABC" 来一步步走一遍。

初始化：

• need = {‘A’: 1, ‘B’: 1, ‘C’: 1}
• window 初始为空：{ }
• valid = 0 // 当前满足要求的字符种类数
• left = 0, right = 0 // 窗口初始为 [0, 0)，左闭右开，开始时窗口内没有字符
• start = 0, len = Infinity // 用来记录最终找到的最小覆盖子串的起始位置和长度

第 1 步：扩大窗口（移动 right）

• right 指向 ‘A’ (索引0)。
  • 将 ‘A’ 加入窗口。window[‘A’] = 1。
  • 检查：window[‘A’] (1) == need[‘A’] (1)？ 相等！所以 valid 加 1，变为 1。
  • valid (1) != need.size (3)，条件不满足，继续扩大。
• right 指向 ‘D’ (索引1)。
  • ‘D’ 不在 t 中，忽略。window 不变，valid 不变。
• right 指向 ‘O’ (索引2)。忽略。
• right 指向 ‘B’ (索引3)。
  • 将 ‘B’ 加入窗口。window[‘B’] = 1。
  • window[‘B’] (1) == need[‘B’] (1)？ 相等！valid 加 1，变为 2。
• right 指向 ‘E’ (索引4)。忽略。
• right 指向 ‘C’ (索引5)。
  • 将 ‘C’ 加入窗口。window[‘C’] = 1。
  • window[‘C’] (1) == need[‘C’] (1)？ 相等！valid 加 1，变为 3。
• 此时，valid (3) == need.size (3)！条件首次满足！ 当前窗口 [0, 5] 即子串 "ADOBEC" 包含了 t 的所有字符。现在记录当前候选子串：start = 0, len = 5 - 0 + 1 = 6。

第 2 步：收缩窗口（移动 left）

• 现在开始移动 left 指针，试图找到一个更小的满足条件的窗口。
• left 指向 ‘A’ (索引0)。
  • 计划将 ‘A’ 移出窗口。
  • 但移出前检查：如果移出 ‘A’，window[‘A’] 将从 1 变为 0。
  • 0 < need[‘A’] (1)，所以 ‘A’ 将不再满足要求，valid 需要减 1，变为 2。
  • 注意：我们先检查，再移出。因为 valid 即将变为 2（小于3），意味着移出后窗口将不再满足条件。所以，在移出之前，当前窗口 "ADOBEC" 是我们以 right=5 为结尾时，能得到的最小满足条件的窗口。
  • 因此，我们更新结果：比较当前窗口长度 6 和之前记录的最小长度 Infinity，6 更小，所以更新 start=0, len=6。
  • 现在，才将 ‘A’ 移出窗口。window[‘A’] = 0。valid = 2。
• 由于 valid != need.size，窗口不再满足条件，我们停止收缩，继续扩大 right。

第 3 步：继续扩大窗口（移动 right）

• right 指向 ‘O’ (索引6)。忽略。
• right 指向 ‘D’ (索引7)。忽略。
• right 指向 ‘E’ (索引8)。忽略。
• right 指向 ‘B’ (索引9)。
  • 将 ‘B’ 加入窗口。window[‘B’] 从 1 变成 2。
  • 检查：2 > need[‘B’] (1)，所以 ‘B’ 本来就是满足的，现在依然满足，valid 不变（仍为2）。
• right 指向 ‘A’ (索引10)。
  • 将 ‘A’ 加入窗口。window[‘A’] 从 0 变成 1。
  • 1 == need[‘A’] (1)？ 相等！valid 加 1，变为 3。
• 此时，valid (3) == need.size (3)！条件再次满足！ 当前窗口是 [1, 10]，即 "DOBECODEBA"。但我们需要找的是最短的。

第 4 步：再次收缩窗口（移动 left）

• 移动 left 试图缩小窗口。
• left 指向 ‘D’ (索引1)。‘D’ 不在 t 中，移出它对 valid 无影响。移出后窗口为 [2, 10] ("OBECODEBA")。valid 仍为 3，条件满足。
  • 更新结果：当前窗口长度是 9，大于之前记录的 len=6，所以结果不更新。
• left 指向 ‘O’ (索引2)。不在 t 中，移出。窗口 [3, 10] ("BECODEBA")，长度 8 > 6，不更新结果。
• left 指向 ‘B’ (索引3)。
  • ‘B’ 在 t 中。移出前检查：window[‘B’] 现在是 2，移出后变为 1。1 >= need[‘B’] (1)，所以 ‘B’ 依然满足要求，valid 不变（仍为3）。
  • 所以可以安全移出。移出后窗口为 [4, 10] ("ECODEBA")，长度 7 > 6，不更新结果。
• left 指向 ‘E’ (索引4)。不在 t 中，移出。窗口 [5, 10] ("CODEBA")，长度 6 = 6，不更新结果。
• left 指向 ‘C’ (索引5)。
  • ‘C’ 在 t 中。移出前检查：window[‘C’] 现在是 1，移出后变为 0。0 < need[‘C’] (1)，所以 ‘C’ 将不满足。
  • 因此，在移出前，窗口 "CODEBA" 是满足条件的。但长度等于之前的最小长度，所以我们可以不更新（或者更新也行，因为题目保证唯一答案）。
  • 现在移出 ‘C’，window[‘C’] = 0, valid 减 1 变为 2。
• 窗口不再满足条件，继续扩大 right。

第 5 步：最后一步

• right 指向 ‘N’ (索引11)。忽略。
• right 指向 ‘C’ (索引12)。
  • 将 ‘C’ 加入窗口。window[‘C’] 从 0 变成 1。
  • 1 == need[‘C’] (1)？ 相等！valid 加 1，变为 3。条件再次满足！
• 现在收缩 left。
• left 指向 ‘O’ (索引6)。不在 t 中，移出。窗口 [7, 12] ("ODEBANC")，长度 6，不更新。
• left 指向 ‘D’ (索引7)。不在 t 中，移出。窗口 [8, 12] ("DEBANC")，长度 5，比6小！ 更新结果！start=8, len=5。
• left 指向 ‘E’ (索引8)。不在 t 中，移出。窗口 [9, 12] ("EBANC")，长度 4，更小！ 更新结果！start=9, len=4。
• left 指向 ‘B’ (索引9)。
  • ‘B’ 在 t 中。移出前检查：window[‘B’] 为 1，移出后为 0。0 < 1，会导致 valid 减少。
  • 所以，在移出前，当前窗口 "BANC" 是满足条件的。记录结果：长度 4 就是我们当前的最小值。
  • 移出 ‘B’，valid 变为 2。
• right 已到末尾，算法结束。

最终结果：从 start=9 开始，长度为 len=4 的子串，即 s.substring(9, 9+4) = "BANC"。

5. 代码实现（JavaScript）

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    // 初始化 need 和 window 计数器
    let need = new Map();
    let window = new Map();

    // 统计 t 中字符的出现次数
    for (let char of t) {
        need.set(char, (need.get(char) || 0) + 1);
    }

    // 滑动窗口指针
    let left = 0, right = 0;
    // 记录满足条件的字符数
    let valid = 0;
    // 记录最小覆盖子串的起始索引和长度
    let start = 0, len = Infinity;

    // 开始滑动窗口
    while (right < s.length) {
        // c 是将移入窗口的字符
        let c = s[right];
        // 扩大窗口
        right++;

        // 进行窗口内数据的一系列更新
        if (need.has(c)) {
            // 更新窗口计数器
            window.set(c, (window.get(c) || 0) + 1);
            // 如果某个字符在窗口中的数量达到了 need 中的要求，则 valid 加一
            if (window.get(c) === need.get(c)) {
                valid++;
            }
        }

        // 判断左侧窗口是否要收缩（当窗口已覆盖 t 时）
        while (valid === need.size) {
            // 更新最小覆盖子串
            if (right - left < len) {
                start = left;
                len = right - left;
            }

            // d 是将移出窗口的字符
            let d = s[left];
            // 缩小窗口
            left++;

            // 进行窗口内数据的一系列更新
            if (need.has(d)) {
                // 如果移出的字符是需要的，并且移出后数量不再满足要求，则 valid 减一
                if (window.get(d) === need.get(d)) {
                    valid--;
                }
                // 更新窗口计数器
                window.set(d, window.get(d) - 1);
            }
        }
    }

    // 返回结果
    return len === Infinity ? "" : s.substring(start, start + len);
};

6. 复杂度分析

• 时间复杂度：O(N)。虽然有两个循环，但每个字符（left 和 right 指针）都只会被遍历一次或两次（进入窗口和离开窗口），所以时间复杂度是线性的。
• 空间复杂度：O(C)。这里 C 是字符集的大小（need 和 window 哈希表的大小），在最坏情况下（t 包含所有字母），复杂度为 O(∣Σ∣)，∣Σ∣ 为字符集大小。

希望这个从暴力解法到滑动窗口优化，再到一步步演示和复杂度分析的详细过程，能帮助你彻底理解这道经典的「最小覆盖子串」问题！