Leetcode 76 Minimum Window Substring

Minimum Window Substring – LeetCode

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 first thing comes into mind is sliding window since this is a substring related problem. The idea is pretty simple actually.

There will be 2 pointers, left and right
We keep moving the right pointer until we find a valid substring
Now we try to move the left string forward to see if we can minimize the length of the substring while keeping the substring valid
As long as we see a valid substring, we update it based on if it’s shorter in length
There are a couple of key catches here:
- Maps/Hash Tables are used to easily check if a letter is there
- There are many ways to denote if the substring becomes valid, e.g it contains all the letters in the target string. Here we are using a simple int variable noOfLettersSeen to denote how may letters has appeared in our sliding window. The tricky thing is when to update it and not update it, as long as the letter showed up less than the targeted value, we increment it by 1, otherwise we do nothing.
- Then we can easily check if the substring becomes valid by checking if the length of noOfLettersSeen equals to the length of the target string s

javascript:

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    let targetMap = {};
    let currentMap = {};
    let result = "";
    let noOfLettersSeen = 0;
    let left = 0;
    let right = 0;

    // construct target map
    t.split("").reduce((acc, c) => {
        if(acc[c]) {
            acc[c] += 1;
        } else {
            acc[c] = 1;
        }
        return acc
    }, targetMap)

    while(right < s.length) {
        // add the current right letter to the current map if it's in the target map
        if(targetMap[s[right]]) {
            if(currentMap[s[right]]) {
                currentMap[s[right]] += 1;
            } else {
                currentMap[s[right]] = 1;
            }

            if(currentMap[s[right]] <= targetMap[s[right]]) {
                noOfLettersSeen++;
            }

            // the substring is valid now, check if we need to move the left pointer
            // as long as moving the left pointer still renders a valid substring, move it. Otherwise stay
            if(noOfLettersSeen === t.length) {
                let valid = true;
                do {
                    if(targetMap[s[left]] && currentMap[s[left]] - 1 >= targetMap[s[left]]) {
                        currentMap[s[left]] -= 1;
                        left++;
                    } else if(targetMap[s[left]] && currentMap[s[left]] - 1 < targetMap[s[left]]) {
                        let newResult = s.slice(left, right + 1);
                        if(!result || newResult.length < result.length) {
                            result = newResult
                        }
                        valid = false;
                    } else {
                        left++;
                    }
                }
                while(valid);
            }
        }

        right++
    }

    return result;
};

Time Complexity:
We looped through both t and s once, so the time complexity is O(m + n)

Space Complexity:
We used maps to store letter counts for s and t, so the space complexity is also O(m + n)

Leetcode 76 Minimum Window Substring

Leetcode 76 Minimum Window Substring

Leave a Reply Cancel reply