76. Minimum Window Substring 🚀

The Question

For this article we will be covering Leetcode's '76. Minimum Window Substring' question. An Advanced Sliding Window Problem.

Question:

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.

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

Explaining The Question

This Question is rated Hard. Which is I would agree with if you haven't solved 424. Longest Repeating Character Replacement as this problem will require a similar solution in structure.

This question requires the use of the Sliding Window technique, where we're attempting to find the shortest window that contains our substring. We then need to return that substring.

---

Recommended Knowledge

1. Sliding Window
2. Hash Map

What do we know?

1. We know that our input will only ever contain uppercase and lowercase english letters.

How we're going to do it:

We're going to go through our list with 2 pointers. Left and Right. Where Left is the start of our current substring and our right is the end of it. Each time we move our right pointer we ask 'Does this window contain our target?' if so we shrink our window by moving our left pointer. We keep doing this until the target is no longer within the window.

We achieve this with the use of Hashmaps and pointers. As well as a little helper function.

1. We firstly turn our target string into a hashmap so we can easily ask later on if we have all the chars required to fit into the target.
2. We also do the same for the input string hashmap, but we leave that empty for now as that hashmap will represent whats in our sliding window.
3. We then create our helper function that let's us know if the current window contains our substring or not. We do this by getting all the chars and their counts from the target hashmap and comparing it with the sliding windows hashmap.
4. We then go through our string, adding it to our hashmap that represents the sliding window.
5. If our current window contains the target, we will shorten our window by reducing our left pointer. Each time checking if this is our new smallest window, if so that becomes our output / return value. We also remove the left pointers hashmap value as it's no longer in the sliding window anymore.

Big O Notation:

• Time Complexity: O(52 * n) | Where 52 of possible chars and where N represents the length of the input itself. The reason it's 52 * n, is because for each item in our string, we're going to be possibly going over a hashmap of 52 length.
• Space Complexity: O(104) | As in the worst case, both of our hashmaps will be totally full. As we have 2 hashmaps that contain up to 52 entries.

Leetcode Results:

See Submission Link:

The Solution

var minWindow = function (s, t) {

    const target_map = new Map();
    const string_map = new Map();
    let shortest = "";

    for (const char of t) {
        target_map.set(char, (target_map.get(char) ?? 0) + 1);
    }

    const substring_contains_target = () => {
        for (const [char, count] of target_map) {
            if (!string_map.has(char) || string_map.get(char) < count) return false;
        }
        return true;
    };

    let left = 0;
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        string_map.set(char, (string_map.get(char) ?? 0) + 1);
        while (substring_contains_target()) {
            const distance = i - left + 1;
            if (shortest == "" || distance < shortest.length) {
                shortest = s.substring(left, i + 1);
            }
            string_map.set(s[left], string_map.get(s[left]) - 1);
            left += 1;
        }
    }

    return shortest;
};