最小覆盖子串

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

注意：

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

示例 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 的子串中，因此没有符合条件的子字符串，返回空字符串。

简单解法：三指针遍历 + Map统计次数暴力求解

进阶解法：使用滑动窗口结合哈希表的方法。该方法通过动态调整窗口边界，并统计窗口内字符频率，高效地找到符合条件的最小子串。

方法思路

统计字符频率：使用哈希表 target 统计 t 中每个字符的出现次数。
初始化窗口：使用左右指针 left 和 right 初始化滑动窗口，并用哈希表 window 统计窗口内字符频率。
移动右指针：扩展窗口，直到包含 t 的所有字符。
收缩左指针：在满足条件的前提下，尽可能收缩窗口，记录最小窗口的位置和长度。
重复步骤3-4：直到右指针到达字符串末尾。

代码实现

function minWindow(s, t) {
    const target = new Map();
    for (const char of t) {
        target.set(char, (target.get(char) || 0) + 1);
    }
    
    const window = new Map(); // 记录当前窗口字符频率
    let valid = 0; // 记录窗口中满足条件的字符个数
    let left = 0, right = 0;
    let start = 0; // 最小覆盖子串的起始位置
    let minLen = Infinity; // 最小覆盖子串的长度
    
    while (right < s.length) {
        const c = s[right];
        right++;
        // 更新窗口数据
        if (target.has(c)) {
            window.set(c, (window.get(c) || 0) + 1);
            if (window.get(c) === target.get(c)) {
                valid++;
            }
        }
        
        // 判断左侧窗口是否需要收缩
        while (valid === target.size) {
            // 更新最小覆盖子串
            if (right - left < minLen) {
                start = left;
                minLen = right - left;
            }
            const d = s[left];
            left++;
            // 更新窗口数据
            if (target.has(d)) {
                if (window.get(d) === target.get(d)) {
                    valid--;
                }
                window.set(d, window.get(d) - 1);
            }
        }
    }
    
    return minLen === Infinity ? "" : s.substring(start, start + minLen);
}

代码解释

统计目标字符频率：使用 target 哈希表记录 t 中每个字符的出现次数。
滑动窗口扩展：右指针 right 不断右移，将字符加入窗口，并更新窗口哈希表 window。当窗口中某个字符的频率达到 target 中的要求时，valid 计数器加1。
滑动窗口收缩：当 valid 等于 target.size 时，说明窗口已包含 t 的所有字符。此时尝试收缩左指针 left，并更新最小窗口的位置和长度。
更新结果：在每次收缩窗口后，记录最小窗口的起始位置和长度，最终返回结果。

复杂度分析

时间复杂度：O(n)，其中 n 是字符串 s 的长度。每个字符最多被访问两次（右指针和左指针各一次）。
空间复杂度：O(k)，其中 k 是字符串 t 中不同字符的个数。主要用于存储哈希表。

示例分析

以 s = "ADOBECODEBANC" 和 t = "ABC" 为例：

初始化：target = {'A': 1, 'B': 1, 'C': 1}，window 为空，valid = 0。
扩展窗口：右指针移动至 D（无影响）、O（无影响）、B（window['B'] = 1，valid = 1）、E（无影响）、C（window['C'] = 1，valid = 2）、O（无影响）、D（无影响）、E（无影响）、B（window['B'] = 2，仍 valid = 2）、A（window['A'] = 1，valid = 3）。
收缩窗口：左指针从 A 开始收缩，移除 A（valid = 2），窗口不再满足条件，继续扩展。
重复扩展和收缩：最终找到最小窗口 "BANC"。

其他解法对比

暴力法：枚举所有子串，检查是否包含 t 的所有字符，时间复杂度 O(n²)，效率低。
优化滑动窗口：本文方法，通过哈希表和双指针动态调整窗口，时间复杂度 O(n)，最优解。

这种方法通过滑动窗口和哈希表的结合，高效地解决了子串覆盖问题，并确保了线性时间复杂度。

方法思路​

代码实现​

代码解释​

复杂度分析​

示例分析​

其他解法对比​