Minimum Window Substring

Given two strings, s and t, find the minimum window substring in s, which has the following properties: 1) It is the shortest substring of s that includes all of the characters present in t. 2) It must contain at least the same frequency of each character as in t. 3) The order of the characters does not matter here.

Note

If there are multiple valid minimum window substrings, return any one of them.

Constraints

• Strings s and t consist of uppercase and lowercase English characters.
• 1 ≤ s.length, t.length ≤ 10³

Examples

Sample Example 1

Input:

• s = "ABAACBAB"
• t = "ABC"

Output: "ACB"

Sample Example 2

Input:

• s = "ACBBACA"
• t = "ABA"

Output: "BACA"

Sample Example 3

Input:

• s = "ABAACBAB"
• t = "ABCC"

Output: ""

Explanation: No substring of s contains all the characters of t (two occurrences of "C" are required, but s has only one), so an empty string is returned.

Solution We can create two map which will store what we want and what our window currently have. Required variable will represent how many unique characters we want and current will represent how many unique characters count matches exactly with freq. We'll itrate over s string updating count in window whenever window count for any character becomes equal to freq count we'll increment current. At any point when we get current is equal to required we'll store current answer and remove left char to shorten the window .

function minWindow(s, t) {

    let freq = new Map();
    let window = new Map();

    // build frequency map
    for (let char of t) {
        freq.set(char, (freq.get(char) || 0) + 1);
    }

    let required = freq.size;
    let current = 0;

    let start = 0;
    let res = [-1, -1];
    let resLen = Infinity;

    for (let end = 0; end < s.length; end++) {

        let char = s[end];

        if (freq.has(char)) {

            window.set(char, (window.get(char) || 0) + 1);

            if (window.get(char) === freq.get(char)) {
                current++;
            }
        }

        while (current === required) {

            if (end - start + 1 < resLen) {
                res = [start, end];
                resLen = end - start + 1;
            }

            let leftChar = s[start];

            if (freq.has(leftChar)) {

                window.set(leftChar, window.get(leftChar) - 1);

                if (window.get(leftChar) < freq.get(leftChar)) {
                    current--;
                }
            }

            start++;
        }
    }

    const [left, right] = res;

    return resLen === Infinity
        ? ""
        : s.slice(left, right + 1);
}

console.log(minWindow('aabccbb', 'bcb'));