x 76. Minimum Window Substring

Loading...LeetCode

time: O(n + m)

space: O(m)

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
    if (s.length < t.length) return '';
    if (s === t) return s;

    const memo = {};
    for (let i = 0; i < t.length; i++) {
        const curr = t[i];
        if (memo[curr] === undefined) {
            memo[curr] = 0;
        }

        memo[curr]++;
    }

    let min = Number.MAX_SAFE_INTEGER;
    let offset = 0;

    let start = 0;
    let end = 0;
    let count = 0;
    while (end <= s.length) {
        const currEnd = s[end];

        if (memo[currEnd] > 0) {
            count++;
        }

        memo[currEnd] !== undefined && memo[currEnd]--;

        while (count === t.length) {
            const d = end - start + 1;
            if (d < min) {
                offset = start;
                min = d;
            }

            const currStart = s[start];
            if (memo[currStart] === 0) {
                count--;
            }
            memo[currStart] !== undefined && memo[currStart]++;
            start++;
        }
        end += 1;
    }

    if (min === Number.MAX_SAFE_INTEGER) {
        return '';
    }

    return s.substring(offset, offset + min);
};