最小覆盖子串

class Solution:
    def minWindow(self , S: str, T: str) -> str:
        # write code here
        dict_ = {}
        min_len = 10001
        n = len(S)
        for i in T:
            dict_[i] = T.count(i)
        l, r = 0, 0
        counter = len(T)
        ans_l, ans_r = 0, 0
        while r<n:
            if S[r] in dict_ and dict_[S[r]]>0:
                counter-=1
            if S[r] in dict_:
                dict_[S[r]]-=1
            if counter==0:
                while l<n:
                    if S[l] in dict_ and dict_[S[l]]<0:
                        dict_[S[l]]+=1
                    elif S[l] in dict_ and dict_[S[l]]==0:
                        if r-l+1<min_len:
                            min_len = r-l+1
                            ans_l, ans_r = l, r+1
                        counter+=1
                        dict_[S[l]]+=1
                        l+=1
                        break
                    l+=1
            
            r+=1
        return S[ans_l:ans_r]

class Solution:
    def minWindow(self , S: str, T: str) -> str:
        # write code here
        if len(S)==0&nbs***bsp;len(T)==0&nbs***bsp;len(S) < len(T):
            return ""
        # 准备两本字典，分别记录T的词频和S子串的词频
        freqT = {}
        freqS = {}
        for string in T:
            if string not in freqT.keys():
                freqT[string] = 1
            else:
                freqT[string] += 1
        q = [] # 准备队列一个，依次记录在S中发现的T字符索引
        cnt = 0 # 计数器， 记录T中字符是否被查全
        length = len(S) + 1
        j = 0
        tail = 0
        head = 0
        while j < len(S):
            if S[j] in freqT.keys():
                # 统计S中子串词频
                if S[j] not in freqS.keys():
                    freqS[S[j]] = 1
                else:
                    freqS[S[j]] += 1
                # 当S的某个单词词频《=T时，表明单词没有查全，计数器加 1，
                if freqS[S[j]] <= freqT[S[j]]:
                    cnt += 1
                # 字符索引入队
                q.append(j)
                # 当单词查全时， 记录长度，同时队头出队，出队单词词频减 1
                while cnt >= len(T):
                    if q[-1] - q[0] + 1 < length:
                        head = q[0]
                        tail = q[-1]
                        length = tail - head + 1
                    s = q.pop(0)
                    freqS[S[s]] -= 1
                    if freqS[S[s]] < freqT[S[s]]:
                        cnt -= 1
            j += 1
        if length == len(S) + 1:
            return ""
        else:
            return S[head:tail+1]

哈希表 + 双指针的滑动窗口，找到包含T的所有字符，缩小窗口找到最小子串
时间复杂度：O(len(T)*len(S)+len(T)) 空间复杂度：O(len(T))

class Solution:
    def check(self, mp):
        for key, value in mp.items():
            if value < 0:
                return False
        return True

    def minWindow(self , S: str, T: str) -> str:
        mp = {}
        low = 0
        high = 0
        left = -1
        right = -1
        len_ = len(S) + 1
        for i in T:
            if i in mp:
                mp[i] -= 1
            else:
                mp[i] = -1
        for j in range(len(S)):
            if S[high] in mp:
                mp[S[high]] += 1
                while self.check(mp):
                    if len_ > high - low + 1:
                        len_ = high - low + 1
                        left = low
                        right = high
                    if S[low] in mp:
                        mp[S[low]] -= 1
                    low += 1
            high += 1
        if left == -1:
            return ''
        return S[left:right+1]

class Solution:
    def minWindow(self , S: str, T: str) -> str:
        # write code here
        
        n = len(S)
        m = len(T)
        if (n == 0&nbs***bsp;m == 0):
            return ''

        # 使用双指针，表示用来匹配T的S子串的左右索引
        index_1 = 0
        index_2 = -1
        
        # min为最短长度子串的左索引， min_len为最短长度
        min = 0
        min_len = n+1
        
        # pattern用字典来记录T中所有字符的出现次数
        # d用来记录双指针中间子串包含pattern中字符的次数
        # lack表示子串要包含T还缺少哪些字符，缺多少个
        d = {}
        pattern = {}
        lack = {}
        
        
        # 把lack和pattern初始化为T中各个字符的出现次数
        # d初始化为0次
        for i in T:
            if i not in d:
                lack[i] = 1
                pattern[i] = 1
                d[i] = 0
            else:
                lack[i] += 1
                pattern[i] += 1
        
        # 如果右指针超过了S的长度，结束循环
        while (index_2 < n):     

            # lack为空也就是S的子串还没有包含所有T
            if (lack != {}):
                
                # 考虑右指针右移的新增字符
                index_2 = index_2 + 1
                if (index_2 >= n):
                    break
                # 如果新增字符在T中
                if (S[index_2] in pattern):
                    # 则d中对应字符的次数加1，lack中对应的减1，
                    # 如果lack中值为0，则表明不再缺了，删除键值
                    d[S[index_2]] += 1
                    if (S[index_2] in lack):
                        lack[S[index_2]] -= 1               
                        if (lack[S[index_2]] == 0):
                            lack.pop(S[index_2])
            
            # 如果lack为空，也就是子串已经包含T
            # 左指针右移，逐渐缩小区间
            else:
                if (index_2 - index_1 + 1 < min_len):
                    min_len = index_2 - index_1 + 1
                    min = index_1
                    
                # 如果删掉的字符在pattern中，则d的对应次数减1
                # 如果d中的出现次数少于pattern中的出现次数
                # 说明子串中该字符比T的要少了，缺少这个字符
                if (S[index_1] in pattern):
                    d[S[index_1]] -= 1
                    if (d[S[index_1]] < pattern[S[index_1]]):
                        lack[S[index_1]] = 1

                index_1 += 1
                
        if (min_len == n+1):
            return ''
        
        return (S[min: min+min_len])