Learning On the Way

76. Minimum Window Substring

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "". Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in s.

def minWindow(self, s: str, t: str) -> str: 
    left = right = 0 
        
    ct = defaultdict(int) 
        
    for c in t: 
        ct[c] += 1 
        
    required = len(ct.items()) 
        
    ans = float('inf'), -1, -1 
        
    incount = 0 
    sct = defaultdict(int) 
    while right < len(s): 
        c = s[right] 
        if ct[c] > 0: 
            sct[c] += 1 
            if sct[c] == ct[c]:     
                incount += 1 
                    
        while left <= right and incount == required: 
            c = s[left] 
            if right - left + 1 < ans[0]: 
                ans = right - left + 1, left, right 
            if ct[c] > 0: 
                sct[c] -= 1 
                if sct[c] < ct[c]: 
                    incount -= 1 
            left += 1 
                
        right += 1 
            
    if ans[1] == float('inf'): 
        return '' 
    else: 
        return s[ans[1] : ans[2] + 1]