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! 🚀