Leetcode - 76. Minimum Window Substring

Javascript Code

/**
 * @param {string} s - The input string
 * @param {string} t - The target string containing required characters
 * @return {string} - The minimum window in s that contains all characters of t
 */

var minWindow = function (s, t) {
    if (t === "") return ""; // Edge case: if t is empty, return an empty string

    let tMap = {}; // Map to store the frequency of characters in t

    // Populate tMap with the count of each character in t
    for (let letter of t) {
        tMap[letter] = (tMap[letter] || 0) + 1;
    }

    let currentMap = {}; // Map to track characters in the current window
    let res = [-1, -1]; // Stores the start and end indices of the smallest valid window
    let have = 0; // Tracks how many unique characters in t are completely matched in the window
    let need = Object.keys(tMap).length; // Total unique characters needed
    let resLength = Infinity; // Stores the length of the smallest valid window
    let l = 0; // Left pointer for the sliding window

    // Expand the window by moving right pointer
    for (let r = 0; r < s.length; r++) {
        let currentLetter = s[r];
        currentMap[currentLetter] = (currentMap[currentLetter] || 0) + 1;

        // If the current character is in t and its frequency matches, increment `have`
        if (tMap[currentLetter] && currentMap[currentLetter] === tMap[currentLetter]) {
            have++;
        }

        // Try to shrink the window from the left while it contains all characters from t
        while (have === need) {
            let currentWindowSize = r - l + 1;

            // Update the result if the current window is smaller than the previously found one
            if (currentWindowSize < resLength) {
                res = [l, r];
                resLength = currentWindowSize;
            }

            // Remove the leftmost character from the window
            currentMap[s[l]]--;

            // If removing s[l] makes the window invalid, decrement `have`
            if (tMap[s[l]] && currentMap[s[l]] < tMap[s[l]]) {
                have--;
            }

            l++; // Move the left pointer forward
        }
    }

    let [start, end] = res;
    // Return the minimum window substring if found, otherwise return an empty string
    return resLength === Infinity ? "" : s.slice(start, end + 1);
};