题解 | #最小覆盖子串#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S string字符串 
# @param T string字符串 
# @return string字符串
#
import sys
class Solution:
    def minWindow(self , S: str, T: str) -> str:
        # write code here
        need_window = {}
        satisfy_window = {}
        need_degree = len(T)
        satisfy_degree = 0
        for c in T:
            need_window[c] = need_window.get(c,0) + 1
        res = sys.maxsize
        start,end=-1,-1
        i,j = -1,-1
        while j<len(S)-1:
            j+=1
            c = S[j]
            if c not in need_window:
                continue
            satisfy_window[c] = satisfy_window.get(c,0) + 1
#             print(satisfy_window)
            if satisfy_window[c] <= need_window[c]:
                satisfy_degree += 1
                if satisfy_degree == need_degree:
                    while satisfy_degree == need_degree:
                        i += 1
                        c = S[i]
                        if c not in need_window:
                            continue
                        satisfy_window[c] -= 1
                        if satisfy_window[c]<need_window[c]:
                            satisfy_degree -= 1
                    if j-i<res:
                        start = i
                        end = j
                        res = j-i
        return S[start:end+1]