滑动窗口，哈希表系列问题

********************************

如有侵权，我会删除。

滑动窗口，哈希表问题模板

window={}
left,right =0, 0
while right <len(s):
	#增大窗口
	window[s[right]]
	right += 1
	while window needs shrink:
    	#缩小窗口
		window[s[left]] -= 1
		left += 1

一、最长不含重复字符的子字符串

    def lengthOfLongestSubstring(self , s: str) -> int:
        # write code here
        #window = {}这样直接用会报错
        from collections import defaultdict
        window = defaultdict(int)
        left,right = 0,0
        res = 0
        # 先移动right，将s字符装进window
        while right<len(s):
            c = s[right]
            right += 1
            window[c] += 1
            #发现当前字符哈希表中已经存在了
            while window[c]>1:
                #收缩左侧窗口
                d = s[left]
                left += 1
                window[d] -= 1
            res = max(res,right-left)
        return res

二、最小覆盖子串

    def minWindow(self, s: str, t: str) -> str:
        from collections import defaultdict
        window = defaultdict(int)#存储窗口里t字符串中各字符出现的个数
        target = defaultdict(int) #存储t字符串中各个字符出现的个数
        valid = 0 #窗口中满足taret条件的字符数
        start,cur_len=0,float('inf')#存储当前最小覆盖子串的起始索引和长度
        left,right = 0,0 #滑动窗口的左右边界
        for c in t:
            target[c]+=1 #t字符串中各个字符出现的个数
        while(right<len(s)): # right不超过s串范围的条件下滑动窗口
            c = s[right] #随着right右移，即将被加入窗口的字符
            right += 1#右移right指针
            if(c in target):#如果待加入窗口的字符在target中
                window[c] += 1#c计入window
                if(window[c] == target[c]):#如果字符进入窗口后，窗口内这个字符的个数和target中这个字符个数一样，就将valid计数加1
                    valid += 1
            while(valid == len(target)):#当前窗口里的子串是可行解
                #更新当前最优值
                if(right-left<cur_len):#找到更短的覆盖子串
                    start = left
                    cur_len = right-left
                d = s[left] #即将被移出窗口的字符
                left += 1#右移left指针
                if(d in target): #如果待移出窗口的字符在target中
                    if(window[d] == target[d]): #如果此时字符d在窗口中出现的次数和在target中出现的次数一样，那么移出d后，valid就要减1。
                        valid -= 1
                    window[d] -= 1 #更新窗口内字符计数
        return "" if cur_len == float('inf') else s[start:start+cur_len]

三、字符串排列

相当于判断s中是否存在一个字串，只包含T中所有字符。

class Solution:
    def checkInclusion(self, t: str, s: str) -> bool:
        from collections import defaultdict
        window,need= defaultdict(int), defaultdict(int)
        for c in t:
            need[c] += 1
        #return need
        left,right = 0, 0
        valid = 0
        while right <len(s):
            c=s[right]
            right += 1
            if c in need:
                window[c] += 1
                if window[c] == need[c]:
                    valid += 1

            while right-left >=len(t): 
                #return  len(need)  
                #判断是否找到了合法子串
                if valid == len(need):
                    return True
                d=s[left]
                left += 1
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
        return False

四、找所有字母异位词

相当于找到s中所有t的排列，并返回起始索引。

class Solution:
    def findAnagrams(self, s: str, t: str) -> List[int]:
        from collections import defaultdict
        window ,need= defaultdict(int), defaultdict(int)
        for c in t:
            need[c] += 1
        #return need
        left,right = 0, 0
        valid = 0
        res = []
        while right <len(s):
            c=s[right]
            right += 1
            if c in need:
                window[c] += 1
                if window[c] == need[c]:
                    valid += 1

            while right-left >=len(t):
            	#当窗口符合条件时，把起始索引加入到res
                if valid == len(need):
                    res.append(left)
                d=s[left]
                left += 1
                #原来用的if need[d]:,结果输出[0]
                #if need[d]:
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
        return res