Leetcode - 76. Minimum Window Substring

Hard

Dec 22, 2025

#sliding-window

76. Minimum Window Substring

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.

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?

Notes

Intuition

Track required character frequencies from t. A window is valid when all frequencies are satisfied (≤ 0 after decrementing). Expand the window to find valid substrings, then shrink to find the minimum.

Implementation

Build a frequency map of characters in t. Process the first window of size len(t), decrementing counts. Slide the window: when valid (all counts ≤ 0), update the minimum and shrink from the left. When invalid or at minimum size, expand from the right. Update the frequency map appropriately when characters enter or leave the window.

Edge-cases

Update order matters: when expanding right, decrement AFTER moving. When shrinking left, increment BEFORE moving. Handle the case where no valid window exists (return empty string).

Time: O(m) — sliding window across s
Space: O(n) — frequency map for characters in t

Complexity

Solution

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(t) > len(s):
            return ""
        
        freq = {}
        for c in t:
            freq[c] = freq[c] + 1 if c in freq else 1


        l, r = 0, len(t) - 1

        for i in range(len(t)):
            if s[i] in freq:
                freq[s[i]] -= 1
        min_window = ""
        while r < len(s):
            is_valid = all(freq[c] <= 0 for c in freq)
            if is_valid:
                curr_window = r - l + 1
                if min_window == "" or curr_window < len(min_window):
                    min_window = s[l:r+1]

                # only slide once we get to minimum length
                if curr_window == len(t):
                    r += 1
                    if r < len(s) and s[r] in freq:
                        freq[s[r]] -= 1
                    
                # reduce window (always look for better)
                if s[l] in freq:
                    freq[s[l]] += 1
                l += 1
            else:
                r += 1
                if r < len(s) and s[r] in freq:
                    freq[s[r]] -= 1
                pass
        
        return min_window
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()