题解 | #最小覆盖子串#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param S string字符串
 * @param T string字符串
 * @return string字符串
 */
function minWindow(S, T) {
    // write code here
    let need = {};
    let win = {};
    for (let ch of T) {
        need[ch] = (need[ch] || 0) + 1;
    }

    let valid = 0,
        needValid = Object.keys(need).length;
    let left = 0,
        right = 0;
    let start = Number.MAX_VALUE,
        len = Number.MAX_VALUE;

    while (right < S.length) {
        let ch = S[right];
        right++;
        if (need[ch]) {
            win[ch] = (win[ch] || 0) + 1;
            if (win[ch] === need[ch]) {
                valid++;
            }
        }

        while (valid === needValid) {
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            let d = S[left];
            left++;
            if (need[d]) {
                if (win[d] === need[d]) {
                    valid--;
                }
                win[d]--;
            }
        }
    }
    return (len === Number.MAX_VALUE ? "" : S.substr(start, len));
}
module.exports = {
    minWindow: minWindow,
};