76.最小覆盖子串 困难

问题：

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 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 的子串中，
因此没有符合条件的子字符串，返回空字符串。

回答：

var minWindow = function(s, t) {
    if (s.length < t.length) return '';
    let map = new Map()
    for (let ch of t) {
        map.set(ch, (map.get(ch) || 0) + 1)
    }
    let need = new Map();
    let sum = 0;
    //开始位置
    let start = 0;
    //最小长度
    let minLen = Infinity;
    let left = 0;
    let right = 0;
    for (right = 0; right < s.length; right++) {
        let val = s[right];
        if (map.has(val)) {
            need.set(val, (need.get(val) || 0) + 1)
            //达到该字母所需数量
            if (need.get(val) == map.get(val)) {
                sum++;
            }
        }
        //当前字符串包含所需子串所有字母，尝试缩小
        while (sum == map.size) {
            //更新最小长度
            if (right - left < minLen) {
                start = left;
                minLen = right - left;
            }
            let leftVal = s[left];
            left++;
            if (map.has(leftVal)) {
                //当前窗口子串字母正好匹配子串字母
                if (need.get(leftVal) == map.get(leftVal)) {
                    sum--;
                }
                //更新该元素数量
                need.set(leftVal, need.get(leftVal) - 1)
            }
        }
    }
    return minLen == Infinity ? '' : s.slice(start, start + minLen + 1)
};