76. Minimum Window Substring - Explanation

Problem Link

Description

Given two strings s and t, return the shortest substring of s such that every character in t, including duplicates, is present in the substring. If such a substring does not exist, return an empty string "".

You may assume that the correct output is always unique.

Example 1:

Input: s = "OUZODYXAZV", t = "XYZ"

Output: "YXAZ"

Explanation: "YXAZ" is the shortest substring that includes "X", "Y", and "Z" from string t.

Example 2:

Input: s = "xyz", t = "xyz"

Output: "xyz"

Example 3:

Input: s = "x", t = "xy"

Output: ""

Constraints:

  • 1 <= s.length <= 1000
  • 1 <= t.length <= 1000
  • s and t consist of uppercase and lowercase English letters.


Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(m) space, where n is the length of the string s and m is the number of unique characters in s and t.


Hint 1

A brute force solution would involve checking every substring of s against t and returning the minimum length valid substring. This would be an O(n^2) solution. Can you think of a better way? Maybe you should think in terms of frequency of characters.


Hint 2

We need to find substrings in s that should have atleast the characters of t. We can use hash maps to maintain the frequencies of characters. It will be O(1) for lookups. Can you think of an algorithm now?


Hint 3

We can use a dynamically sized sliding window approach on s. We iterate through s while maintaining a window. If the current window contains at least the frequency of characters from t, we update the result and shrink the window until it is valid.


Hint 4

We should ensure that we maintain the result substring and only update it if we find a shorter valid substring. Additionally, we need to keep track of the result substring's length so that we can return an empty string if no valid substring is found.


Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Brute Force

Intuition

We want the smallest substring of s that contains all characters of t (with the right counts).
The brute-force way is to try every possible substring of s and check whether it covers all the characters in t.
For each starting index, we expand the end index and keep a frequency map for the current substring.
Whenever the substring has all required characters, we see if it's the smallest one so far.
This is simple to understand but very slow because we check many overlapping substrings.

Algorithm

  1. If t is empty, return an empty string.
  2. Build a frequency map countT for all characters in t.
  3. Initialize:
    • res = [-1, -1] to store the best window,
    • resLen = infinity to store the smallest length found.
  4. For each starting index i in s:
    • Create an empty frequency map countS.
    • For each ending index j from i to the end of s:
      • Add s[j] to countS.
      • Check if the current substring from i to j contains all characters in t:
        • For each character c in countT, ensure countS[c] is at least countT[c].
      • If it satisfies all requirements and is smaller than the current best, update res and resLen.
  5. After all checks:
    • If resLen is still infinity, return "".
    • Otherwise, return the substring s[res[0] : res[1] + 1].
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if t == "":
            return ""

        countT = {}
        for c in t:
            countT[c] = 1 + countT.get(c, 0)

        res, resLen = [-1, -1], float("infinity")
        for i in range(len(s)):
            countS = {}
            for j in range(i, len(s)):
                countS[s[j]] = 1 + countS.get(s[j], 0)

                flag = True
                for c in countT:
                    if countT[c] > countS.get(c, 0):
                        flag = False
                        break

                if flag and (j - i + 1) < resLen:
                    resLen = j - i + 1
                    res = [i, j]

        l, r = res
        return s[l : r + 1] if resLen != float("infinity") else ""

Time & Space Complexity

  • Time complexity: O(n2∗m)O(n ^ 2 * m)
  • Space complexity: O(m)O(m)

Where nn is the length of the string ss and mm is the total number of unique characters in the strings tt and ss.

2. Sliding Window

Intuition

We want the smallest window in s that contains all characters of t (with the right counts).
Instead of checking all substrings, we use a sliding window:

  • Expand the window by moving the right pointer r and adding characters into a window map.
  • Once the window has all required characters (i.e., it "covers" t), we try to shrink it from the left with pointer l to make it as small as possible while still valid.

During this process, we keep track of the best (smallest) window seen so far.
This way, we only scan each character at most two times, making it efficient and still easy to follow.

Algorithm

  1. If t is empty, return "".
  2. Build a frequency map countT for characters in t.
  3. Initialize:
    • window as an empty map for the current window counts.
    • have = 0 = how many characters currently meet the required count.
    • need = len(countT) = how many distinct characters we need to match.
    • res = [-1, -1] and resLen = infinity to store the best window.
  4. Use a right pointer r to expand the window over s:
    • Add s[r] to window.
    • If s[r] is in countT and its count in window matches countT, increment have.
  5. When have == need, the window is valid:
    • Update the best result if the current window is smaller.
    • Then shrink from the left:
      • Decrease the count of s[l] in window.
      • If s[l] is in countT and its count in window falls below countT, decrement have.
      • Move l right.
  6. After the loop, return the substring defined by res if found; otherwise, return "".
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if t == "":
            return ""

        countT, window = {}, {}
        for c in t:
            countT[c] = 1 + countT.get(c, 0)

        have, need = 0, len(countT)
        res, resLen = [-1, -1], float("infinity")
        l = 0
        for r in range(len(s)):
            c = s[r]
            window[c] = 1 + window.get(c, 0)

            if c in countT and window[c] == countT[c]:
                have += 1

            while have == need:
                if (r - l + 1) < resLen:
                    res = [l, r]
                    resLen = r - l + 1

                window[s[l]] -= 1
                if s[l] in countT and window[s[l]] < countT[s[l]]:
                    have -= 1
                l += 1
        l, r = res
        return s[l : r + 1] if resLen != float("infinity") else ""

Time & Space Complexity

  • Time complexity: O(n+m)O(n + m)
  • Space complexity: O(m)O(m)

Where nn is the length of the string ss and mm is the total number of unique characters in the strings tt and ss.