76. Minimum Window Substring

Minimum Window Substring

Problem Description

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 test cases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

 

Example 1:

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

Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"

Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""

Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

 

Constraints:

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s and t consist of uppercase and lowercase English letters.

 

Follow up: Could you find an algorithm that runs in O(m + n) time?

Approach) Sliding Window

1. From the name of the problem, you see a "window" in it.
2. So basically it's trying to give us a hint, that is, we should find some "window" that contains all the characters in t and it has the shortest length.
3. So, sliding window algorithm.
4. Sliding window is a very useful technique that involves a left and right pointer, and by moving the left and right pointers, we can find each possible window that satisfies our constraint that it should contain all the characters in t.
5. So how do we know if a window contains all characters in t?
6. We can definitely use a counter and hash map that records how many times each character appears in t.
7. For example, for t = aabc, we know frequencies = { a: 2, b: 1, c: 1 } and count = 4. It means we need to find a substring in s that contains 4 characters that are 2 as, 1 b and 1 c.
8. Initialize l = 0, r = 0, count = 0. l is the left pointer, r is the right pointer and count is how many character we collected for t so far. By moving the right pointer r, when we meet one character of t in s, we can increment count and frequencies of each character. But we only increment count of the character if its frequency is still greater than 0.
9. For example, at a certain point, we have { a: 2 }. It means, to cover the character a in t, we still need the substring in s to contain 2 as. However, once it becomes 0, we can still decrement its frequency in the map, but we cannot increment count, because it does not count as one character that we must cover.
10. But what does the negative frequency in the map mean? It means that we covered more as than necessary in the substring in s for t.
11. So when count == t.length, we know that we covered all characters in t. We can find the start index and its length.
12. Also we will try moving l forward to squeeze it, and we might find an even smaller window.
13. Notice that we only decrement count for character, for example, a, when frequency of a becomes greater than or equal to 0. It means, when you move l forward, you'll miss one a, so one less character in t we counted so far.
14. Think of the frequency map and count are some kind of state. When count == t.length, we know we find a window that can cover every character in t, but it could be smaller if the character at the left end is not a must-include.

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
const minWindow = function (s, t) {
  if (!s || !t || s.length < t.length) return "";

  let l = 0, r = 0;
  let count = 0, minI = s.length + 1, minL = s.length + 1;

  const freqMap = {};
  for (const ch of t) freqMap[ch] = (freqMap[ch] || 0) + 1;

  while (r < s.length) {
    if (freqMap[s[r]]-- >= 1) count += 1;
    r += 1;

    while (count == t.length) {
      if (r - l < minL) {
        minL = r - l;
        minI = l;
      }
      if (freqMap[s[l]]++ >= 0) count -= 1;
      l += 1;
    }
  }
  return s.slice(minI, minI + minL);
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #76. Minimum Window Substring

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!