LC76. Minimum Window Substring

Approach 1: Optimal

import math
from collections import Counter
 
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if t == "": return ""
 
        tCounts, windowCounts = Counter(t), Counter()
        have, want = 0, len(t)
        subL, subR, subLen = -1, -1, float("inf")
 
        l = 0
        for r in range(len(s)):
            rc = s[r]
            windowCounts[rc] += 1
 
            # Remember duplicates from target string are allowed. We're
            # going to keep incrementing `have` as we find each character
            # (including duplicates) until have == want. As soon as we
            # increment from previous line, we can increment have as long
            # as count of right char doesn't exceed the count in target string.
            if windowCounts[rc] <= tCounts[rc]:
                have += 1
            
            while have == want:
                # Check if we have a new minimum substring that satisfies
                # criteria. If yes, store the range indices and length.
                if (r - l + 1) < subLen:
                    subLen = r - l + 1
                    subL, subR = l, r
 
                # At this point, we can slide window from left edge to see if
                # a smaller substring satisfies the same condition. But when we increment
                # left, we lose previous left char from window and thus window count
                # must be updated first.
                windowCounts[s[l]] -= 1
 
                # After we lose old left char, we should decrement `have` if
                # we don't have surplus over target's left char count in window.
                if windowCounts[s[l]] < tCounts[s[l]]:
                    have -= 1
 
                # And we finally increment left to slide the window.
                l += 1
        
        return s[subL:subR + 1] if not math.isinf(subLen) else ""

Complexity

Time: $O(n)$
Space: $O(1)$

Other Languages