Minimum Window Substring

StringSliding Window

30 min

Problem Statement

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 "".

Example

Example 1:

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

s = "ADOBECODEBANC", t = "ABC"

Minimum Window Substring: "BANC"

Output: "BANC"

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

Solution (Sliding Window)

This problem is a classic application of the sliding window technique. We use two pointers to form a window and a hash map to keep track of the characters needed from string t.

Algorithm Steps

Create a hash map to store the character counts of string t.
Initialize a window map, left and right pointers, and variables to track the number of characters needed and found.
Expand the window by moving the right pointer. If a character from t is found, update the counts.
Once all characters from t are in the window, start shrinking the window from the left.
While shrinking, if a character from t is removed, update the counts.
Keep track of the minimum window found so far.

Minimum Window Substring

Sliding Window Approach

Progress1 / 1

Ready to start the visualization

String `s`

`t` Frequency Map

Window Frequency Map

Minimum Window

N/A

Minimum Window Substring Solution


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 ""