76. 最小覆盖子串

题目链接：https://leetcode.cn/problems/minimum-window-substring/

代码

/**
 * 76. 最小覆盖子串
 * https://leetcode.cn/problems/minimum-window-substring/
 */

function minWindow(s: string, t: string): string {
    // 维护s滑动窗口现有字符及数量，t的字符及数量，a-z 0-25 / A-Z 26-51
    const sArr = new Array(52).fill(0), tArr = new Array(52).fill(0);
    const len = s.length;
    let cnt = 0; // 还需要匹配的字符种类数
    let res = '';
    // 初始化tArr
    for (const x of t) {
        const index = getIdx(x);
        tArr[index]++;
        if (tArr[index] === 1) cnt++;
    }
    for (let i = 0, j = 0; i < len; i++) {
        const right = getIdx(s[i]);
        sArr[right]++;
        if (sArr[right] === tArr[right]) cnt--; // 当前字符达到所需数量
        while (j < i) {
            const left = getIdx(s[j]);
            // 当前字符多了，移动左指针
            if (sArr[left] > tArr[left]) {
                sArr[left]--;
                j++;
            }
            else break;
        }
        // 已全部匹配，是第一次匹配或比之前的匹配窗口更短
        if (cnt === 0 && (!res || res.length > i - j + 1)){
            res = s.substring(j, i + 1);
        }
    }
    return res;
}

// 传入单字符，返回索引
function getIdx(x: string): number {
    return x >= 'A' && x <= 'Z' // 判断大小写
        ? x.charCodeAt(0) - 'A'.charCodeAt(0) + 26
        : x.charCodeAt(0) - 'a'.charCodeAt(0);
}

思路

利用滑动窗口 + 计数数组：

• 预处理字符串 t，用 tArr 记录每种字符需要的数量，同时统计还需要匹配的字符种类数 cnt；
• 遍历 s 作为右边界 i，更新窗口内计数 sArr，当某个字符数量满足要求时，让 cnt--；
• 当 cnt === 0 时，说明当前窗口已经覆盖了 t 所有字符，此时尝试移动左指针 j，尽可能缩小窗口；
• 在所有满足条件的窗口中，记录最短的那个。

这里用一个简单的字符映射，把 a-z 映射到 0-25，A-Z 映射到 26-51。

• 时间复杂度 $O(|s|+|t|)$，遍历字符串 s 一次，每个字符最多进窗口一次、出窗口一次，预处理 t 需要 $O(|t|)$
• 空间复杂度 $O(1)$，只使用了固定大小的计数数组（52 个元素）和几个变量