[LeetCode] 76. Minimum Window Substring

Problem : https://leetcode.com/problems/minimum-window-substring/

Use sliding window based approach. Firstly expand window to find the longest substring contains all characters of target string. Then shrink window to find the valid shortest substring.

Time Complexity : O ( S + T ) 

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        counter = Counter(t)
        
        right = 0
        seen = defaultdict(int)
        count = 0
        
        windowStart = -1
        windowSize = 2 ** 31 - 1
        
        for left in range(len(s)):
            while right < len(s) and count < len(counter):
                seen[s[right]] += 1
                
                if seen[s[right]] == counter[s[right]]:
                    count += 1
                
                right += 1
            
            if count == len(counter):
                if windowSize > right - left:
                    windowStart = left
                    windowSize = right - left
            
            seen[s[left]] -= 1
            if seen[s[left]] == counter[s[left]] - 1:
                count -= 1
            
        
        if windowStart == -1: 
            return ""
        
        return s[windowStart:windowStart + windowSize]