Minimum Window Substring

Problem

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

m == s.length
n == t.length
1 <= m, n <= 10⁵
s and t consist of uppercase and lowercase English letters.

Solution

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    const map = {}; // count of characters in t not matched by our window
    let count = 0; // number of positive values in map
    let l = 0; // left of window
    let r = 0; // right of window
    const res = { start: -Infinity, end: Infinity }; // current min window start/end index

    // fill in initial values of map
    for (const c of t) {
        if (!(c in map)) {
            map[c] = 0;
            count++;
        }
        map[c]++;
    }

    // find minimum window
    for (; r < s.length; r++) {
        if (s[r] in map) {
            map[s[r]]--;
            if (!map[s[r]]) { // s[r] value in map is 0
                count--;
            }
        }

        while (!count) { // slide l until window is no longer valid
            if (r - l < res.end - res.start) { // possible new min window
                res.end = r;
                res.start = l;
            }
            if (s[l] in map) {
                if (!map[s[l]]) { // s[l] value in map is 0
                    count++;
                }
                map[s[l]]++;
            }
            l++;
        }
    }
    return res.end === Infinity ? "" : s.substring(res.start, res.end + 1);
};

We will implement a sliding window solution. We use map to keep track the number of each unique character in t that are not in our window s[l:r + 1], and count to cache how many values in map are positive. To begin, we slide r until our window is valid (ie. count is 0). Next, we proceed by sliding l until the window is no longer valid. While sliding l, we check if any of the intermediate windows (which are valid) is smaller in size than res and update accordingly.

Problem​

Solution​

Problem

Solution