题解 | #最小覆盖子串#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S string字符串 
# @param T string字符串 
# @return string字符串
#
class Solution:
    def minWindow(self , S: str, T: str) -> str:
        # write code here
        import collections
        if len(S) < len(T):
            return ''
        cnt = collections.Counter(T)
        need = len(T)
        start,end = 0,-1
        l = r = 0
        min_len = len(S) + 1
        for r in range(len(S)):
            ch = S[r]
            if ch in cnt:
                if cnt[ch] > 0:
                    need -= 1
                cnt[ch] -= 1
            while need == 0:
                lens = r - l + 1
                if lens < min_len:
                    min_len = lens
                    start,end = l,r
                
                ch = S[l]
                if ch in cnt:
                    if cnt[ch] >= 0:
                        need += 1
                    cnt[ch] += 1
                l += 1
        
        return S[start:end + 1]

滑动窗口的较难的题目，当T所有字符的出现后开始while循环不断缩小边界，使得边界尽可能短，并更新长度和起始位置，要注意左端点移动时need和cnt的变化。