LeetCode Challenge: 76. Minimum Window Substring - JavaScript Solution 🚀

Top Interview 150

The Minimum Window Substring problem requires finding the smallest substring of s that contains all characters from t. Let’s solve it step by step using an efficient sliding window approach.

---

🚀 Problem Description

Given strings s and t, return the smallest substring of s such that all characters in t (including duplicates) are included in the substring. If no such substring exists, return an empty string "".

---

💡 Examples

Example 1

Input: s = "ADOBECODEBANC", t = "ABC"  
Output: "BANC"  
Explanation: The substring "BANC" contains all characters 'A', 'B', and 'C'.

Example 2

Input: s = "a", t = "a"  
Output: "a"  
Explanation: The entire string `s` matches `t`.

Example 3

Input: s = "a", t = "aa"  
Output: ""  
Explanation: `t` requires two 'a's, but `s` only has one.

---

🏆 JavaScript Solution

We will solve this using a sliding window and hash maps to keep track of character frequencies.

---

Implementation

var minWindow = function(s, t) {
    if (s.length < t.length) return "";

    const tFrequency = {};
    for (let char of t) {
        tFrequency[char] = (tFrequency[char] || 0) + 1;
    }

    let left = 0;
    let right = 0;
    let formed = 0;
    const windowFrequency = {};
    let minLength = Infinity;
    let minWindow = "";

    const required = Object.keys(tFrequency).length;

    while (right < s.length) {
        const char = s[right];
        windowFrequency[char] = (windowFrequency[char] || 0) + 1;

        if (tFrequency[char] && windowFrequency[char] === tFrequency[char]) {
            formed++;
        }

        while (formed === required) {
            if (right - left + 1 < minLength) {
                minLength = right - left + 1;
                minWindow = s.substring(left, right + 1);
            }

            const leftChar = s[left];
            windowFrequency[leftChar]--;
            if (tFrequency[leftChar] && windowFrequency[leftChar] < tFrequency[leftChar]) {
                formed--;
            }
            left++;
        }

        right++;
    }

    return minWindow;
};

---

🔍 How It Works

1. Frequency Map for t:

   • Create a hash map tFrequency to store the count of each character in t.

2. Sliding Window:

   • Use two pointers (left and right) to define a dynamic window in s.
   • Expand the window by moving right.
   • Contract the window by moving left when all characters in t are present.

3. Update Minimum Window:

   • When the window contains all characters in t (i.e., formed === required), check if it’s the smallest window so far.

4.Return Result:

• Return the smallest substring stored in minWindow.

---

🔑 Complexity Analysis

• Time Complexity: O(m+n), where m is the length of s and n is the length of t.

  • Each character in s is processed at most twice (once by right and once by left).

• Space Complexity: O(n+m), where n is the size of tFrequency and m is the size of windowFrequency.

---

📋 Dry Run

Input: s = "ADOBECODEBANC", t = "ABC"

Output: "BANC"

---

✨ Pro Tips for Interviews

1. Explain Sliding Window:

   • Highlight its efficiency in reducing unnecessary computations by dynamically adjusting the window size.

2. Discuss Edge Cases:

   • s shorter than t.
   • Characters in t not in s.
   • Multiple valid substrings with the same minimum length.

3. Highlight Efficiency:

   • Compare this O(m+n) solution with naive O(m⋅n) approaches that check all substrings.

---

📚 Learn More

Check out the full explanation and code walkthrough on my previous Dev.to post:
👉 Substring with Concatenation of All Words - JavaScript Solution

What’s your approach to solving this problem? Let’s discuss! 🚀

---

Comments

[Rahul Kumar Barnwal]

Follow Me on GitHub 🚀

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!