题解 | #最小覆盖子串#

#
# 
# @param S string字符串 
# @param T string字符串 
# @return string字符串
#
# 滑动窗口的基本思想：

# 用两个字典分别维护窗口中字符的统计数量、以及被求解子串中字符的统计数量
# 用双指针遍历主字符串，双指针的初始值均为0，窗口的范围是[left, right)（左闭右开）
# 遍历过程中，不断增大、缩小窗口，并更新状态
class Solution:
    def minWindow(self , S , T ):
        # write code here
        window=dict()
        target=dict()
        for t in T:
            if t in target.keys():
                target[t]+=1
            else:
                target[t]=1
        match=0
        left=0
        right=0
        start=0
        minlen=99999
        while right<len(S):
            c=S[right]
            right+=1
            if c in target.keys():
                if c in window.keys():
                    window[c]+=1
                else:
                    window[c]=1
                if window[c]==target[c]:
                    match+=1
            while match==len(target):
                if right-left<minlen:
                    minlen=right-left
                    start=left
                c=S[left]
                left+=1
                if c in target.keys():
                    if window[c]==target[c]:
                        match-=1
                    window[c]-=1
        if minlen==99999:
            return ""
        return S[start:start+minlen]