#76. Minimum Window Substring

https://leetcode.com/problems/minimum-window-substring/description/?envType=daily-question&envId=2024-02-04

function minWindow(source, target) {
    // Initialize arrays to keep track of character frequency in `target`
    // and the current window in `source`
    const targetFreq = new Array(128).fill(0);
    const windowFreq = new Array(128).fill(0);

    // Populate target character frequencies
    for (const char of target) {
        ++targetFreq[char.charCodeAt(0)];
    }

    let validCharCount = 0; // Keeps track of how many characters match target in current window
    let left = 0; // Left pointer for the sliding window
    let start = -1; // Start index of the min-length window
    let minLength = Infinity; // Length of the smallest window found

    // Iterate over the `source` string to find the minimum window
    for (let right = 0; right < source.length; ++right) {
        // Include the current character in the window
        const rightCharIndex = source.charCodeAt(right);
        ++windowFreq[rightCharIndex];

        // If the character is needed and the window has enough of that character, increase the valid count
        if (windowFreq[rightCharIndex] <= targetFreq[rightCharIndex]) {
            ++validCharCount;
        }

        // Try and contract the window from the left if it contains all the required characters
        while (validCharCount === target.length) {
            if (right - left + 1 < minLength) {
                minLength = right - left + 1; // Update the smallest window length
                start = left; // Update the start index of the smallest window
            }

            // Decrease the left-most character's frequency and move the left pointer
            const leftCharIndex = source.charCodeAt(left);
            if (targetFreq[leftCharIndex] >= windowFreq[leftCharIndex]) {
                --validCharCount; // If the character was contributing to the valid count, decrease the valid count
            }
            --windowFreq[leftCharIndex];
            ++left;
        }
    }

    // If `start` is not updated, no valid window is found
    // Otherwise, return the minimum length window from `source`
    return start < 0 ? '' : source.slice(start, start + minLength);
}

I understand some part of this question but not all. I understand because some parts had appeared in some questions I have solved before and for the parts I do not get yet, it is because of impatient. No enough time to go through patiently, but there will be more than enough time soon tho.

I also found a platform that already answered many, if not all leetcode questions. i think their answers are great based off of this particular hard question.

It is AlgoMonster, although some product are paid tho.