题解 | 最小覆盖子串

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param S string字符串
 * @param T string字符串
 * @return string字符串
 */
function minWindow(S, T) {
    // write code here
    const m = T.length
    // 记录T里面每一种字母有多少种
    const T_a = new Map
    // T里面的字母有多少种
    let T_c = 0
    for (let i = 0; i < m; i++) {
        if (!T_a.has(T[i])) T_c++
        T_a.set(T[i], (T_a.get(T[i]) || 0) + 1)
    }

    let l = 0
    let r = 0
    const n = S.length

    let min = Infinity
    let res;
    while (r < n) {
        if (T_a.has(S[r])) T_a.set(S[r], (T_a.get(S[r]) || 0) - 1)
        // 等于0，表示当前字母在S里面数量合适了
        if (T_a.get(S[r]) === 0) T_c--
        // 如果所有的字母都在T里面有了，获取最短的字符串
        while (T_c === 0 && l <= r) {
            if (r - l + 1 < min) {
                min = r - l + 1
                res = [l, r]
            }
            if (T_a.has(S[l])) {
                if (T_a.get(S[l]) === 0) T_c++
                T_a.set(S[l], (T_a.get(S[l]) || 0) + 1)
            }
            l++
        }
        r++
    }

    return min === Infinity ? '' : S.slice(res[0], res[1] + 1)

}
module.exports = {
    minWindow: minWindow,
};