题解 | #最小覆盖子串#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S string字符串 
# @param T string字符串 
# @return string字符串
#
class Solution:
    def minWindow(self , S: str, T: str) -> str:
        # write code here

        left = 0
        right = 0
        lack = {}
        has = {}
        need = {}
        for i in T:
            if i not in lack.keys():
                lack[i]=1
            else:
                lack[i]+=1
            need[i]=lack[i]
            has[i]=0
        if S[0] in lack.keys():
            if lack[S[0]]==1:
                lack.pop(S[0])
            else:
                lack[S[0]]-=1
            has[S[0]]=1
        minc = 99999999
        minthis = [left,right]
        while left<=right or right < len(S)-1:
            if right==len(S)-1 and len(lack.keys())>0:
                break
            if len(lack.keys())==0:
                leg = right-left+1
                if leg<minc:
                    minthis = [left,right]
                    minc = leg
                if S[left] in has.keys():
                    has[S[left]]-=1
                    if has[S[left]]<need[S[left]]:
                        if S[left] not in lack.keys():
                            lack[S[left]]=1
                        else:
                            lack[S[left]]+=1
                left +=1
            elif right < len(S)-1:
                right +=1
                if S[right] in lack.keys():
                    lack[S[right]]-=1
                    if lack[S[right]]==0:
                        lack.pop(S[right])
                if S[right] in T:
                    has[S[right]]+=1
        
        if minc<99999999:
            return S[minthis[0]:minthis[1]+1]
        else:
            return ''