76. Minimum Window Substring

'''
watch neetcode video beautiful explanation
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 "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.
'''
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        countT={}
        window={}
        l=0
        res=[-1,-1]
        reslen=float('inf')
        have,need=0,0

        for i in t:
            countT[i]=countT.get(i,0)+1

        need=len(countT)

        for r in range(len(s)):
            c=s[r]
            window[c]=window.get(c,0)+1
            if c in countT and countT[c]==window[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=have-1
                l=l+1
        l,r=res
        return s[l:r+1] if reslen!=float('inf') else ""