Minimum Window Substring

Intuition

We keep a frequency map of exactly what characters t demands and how many of each. As a right pointer expands the window, we increase the counts of characters we have collected and maintain a match counter that tracks how many distinct requirements are fully satisfied. The moment every requirement is met, the window is valid, so we try to shorten it by advancing a left pointer, giving back characters until some requirement is no longer satisfied. Every time the window is valid we compare its length with the best seen and record the smallest. Because each pointer only moves forward, the whole scan is linear.

Algorithm walkthrough

1. 1Build a need map from t: the count of each required character, and set required to the number of distinct characters.
2. 2Expand the right pointer one character at a time, incrementing that character's count in the window map.
3. 3Whenever a character's window count reaches its needed count, increment have; when have equals required the window covers all of t.
4. 4While the window is valid, record it if it is shorter than the best window found so far, then move the left pointer forward and decrement the leaving character's count.
5. 5If dropping the leaving character makes its count fall below what is needed, decrement have so the window becomes invalid again and expansion resumes.
6. 6After the right pointer reaches the end, return the recorded best window, or "" if none was ever valid.

Implementation

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""
        need = {}
        for c in t:
            need[c] = need.get(c, 0) + 1
        required = len(need)
        window = {}
        have = 0
        best_len = float("inf")
        best_left = 0
        left = 0
        for right, c in enumerate(s):
            window[c] = window.get(c, 0) + 1
            if c in need and window[c] == need[c]:
                have += 1
            while have == required:
                if right - left + 1 < best_len:
                    best_len = right - left + 1
                    best_left = left
                lc = s[left]
                window[lc] -= 1
                if lc in need and window[lc] < need[lc]:
                    have -= 1
                left += 1
        return "" if best_len == float("inf") else s[best_left:best_left + best_len]