76.-minimum-window-substring.md

76. Minimum Window Substring

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        ## 首先这是一道hard的题!
        ## 为什么是hard 比昨天难, 为什么咧?
        ## 因为返回要求的是str, 不是返回两个指针 diff 的最大值,
        ## 而是要记录具体指针的位置,然后返回
        start, l, r = 0, 0, 0
        windows = collections.defaultdict(int)
        tdict = {k:t.count(k) for k in t}
        match = 0
        minLen = 2 << 31
        while r < len(s):
            w = s[r]
            if w in tdict:
                windows[w] += 1
                if windows[w] == tdict[w]:
                    match += 1
            r += 1
            
            ## 集齐所有元素
            while match == len(tdict):
                if r - l < minLen:
                    minLen = r - l 
                    start = l # 更换ans 的起始index
                w2 = s[l]
                if w2 in tdict:
                    windows[w2] -= 1
                    if windows[w2] < tdict[w2]:
                        match -= 1
                l += 1
        return s[start:start + minLen] if minLen != 2 << 31 else ""