76. Minimum Window Substring

[Tcdian]

76. Minimum Window Substring

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

Example

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Node

• 如果 S 中不存这样的子串，则返回空字符串 ""。
• 如果 S 中存在这样的子串，我们保证它是唯一的答案。

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    const cacheT = new Map();
    for (let i = 0; i < t.length; i++) {
        cacheT.set(t[i], (cacheT.get(t[i]) || 0) + 1 );
    }
    let result = '';
    let minLen = Infinity;
    const cacheS = new Map();
    let count = 0;
    for (let left = 0, right = 0; right < s.length; right++) {
        if (cacheT.has(s[right])) {
            cacheS.set(s[right], (cacheS.get(s[right]) || 0) + 1);
            if (cacheS.get(s[right]) <= cacheT.get(s[right])) {
                count++;
            }
        }
        if (count === t.length) {
            while(!cacheS.has(s[left]) || cacheS.get(s[left]) > cacheT.get(s[left])) {
                if (cacheS.has(s[left])) {
                    cacheS.set(s[left], cacheS.get(s[left]) - 1);
                }
                left++;
            }
            if (right - left + 1 < minLen) {
                result = s.slice(left, right + 1);
                minLen = right - left + 1;
            }
            cacheS.set(s[left], cacheS.get(s[left]) - 1);
            left++;
            count--;
        }
    }
    return result;
};