题解 | #最小覆盖子串#

初始化左右指针begin= end= 0，把索引区间 [begin, end] 称为一个「窗口」。
不断地增加end指针扩大窗口 [begin, end] ，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
此时，停止增加end，转而不断增加 begin 指针缩小窗口 [begin, end] ，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

现在问题在于，怎么计算窗口中的字符串符合要求呢？

创建一个map存放T串中每个字符出现的次数，如T=abbc的时候map为{a:1,b:2,c:1}。
创建一个counter表示map中每个元素是否在窗口中集齐（对应的map小于等于0表示集齐），每集齐一个，counter就减1，直到counter为0表示全部集齐。
然后进行增加end的时候，判断end指向的数据S[end]是否存在map中，如果存在的话，就把map[S[end]]减一，表示S[end]已经拥有了一个。
直到map[S[end]]<=0表示S[end]集齐，此时counter可以减1。
当counter为0表示此时的窗口含有全部的T元素。

————————————————
版权声明：本文为CSDN博主「Doe」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_43613849/article/details/117714397

#
# 
# @param S string字符串 
# @param T string字符串 
# @return string字符串
#
class Solution:
    def minWindow(self , S , T ):
        # write code here
        c,l = 0,0##指针
        res = ""##设置的小窗口
        min_l = len(S) + 1
        d = {}

        for i in T:
            d[i] = d.get(i,0) + 1
        for r in range(len(S)):
            if S[r] in T: 
                if d[S[r]]>0:
                    c += 1
                d[S[r]] = d[S[r]] - 1  ##S[r]在新的窗口中，就减1，，表示已经拥有了一个
#                 print(d[S[r]])
            while c==len(T):##缩小串口范围
                if S[l] in T:
                    if min_l > r-l+1:
                        min_l = r-l+1
                        res = S[l:r+1]
                    d[S[l]] = d[S[l]] + 1
                    if d[S[l]]>0:##表示c对应的元素是否已经在窗口中集齐，集齐一个减一个
                        c -= 1
#                     print(S[l])
                l += 1
        return res