最小覆盖子串(滑动窗口+哈希)

# 思路：
### 1右移右指针 直至窗口全覆盖子串
### 2右移左指针 缩小窗口，并不断地检查窗口是否覆盖子串，
### 3如果是的话，就更新起始位置strStart和窗口长度
### 4如果不是的话，就右移右指针right，重复1操作
### 最后根据起始位置strStart和窗口长度windowLength来输出最短字符串

class Solution:
    def minWindow(self, S, T):
        # write code here
        if len(S) < len(T):
            return ""
#       把T中的所有字符串全部存入数组中去
        hashmap = {}
        for c in T:
            hashmap[c] = hashmap.setdefault(c, 0) + 1  # need = {字符:出现次数}
#       定义窗口的左右边界
        left = 0
        right = 0
#       定义满足条件的起始位置和窗口长度：
        strStart = 0
        windowLength = len(S) + 1
#       定义检查函数：检查窗口是否吧字符串t全部覆盖了，如果map中的值全都不大于0，则全部覆盖了。
#       hashmap的values表示表示需要的key是多少，值大于零：需要1个，如果小于0表示窗口的key已经充足了，不再需要了。
#       hashmap中key:valuse=表示key需要values个。
        def check(map1):
            for i in map1.values():
                if i > 0:
                    return False
            return True

        while right < len(S):
#           记录右指针的位置的字符
            rightChar = S[right]
#           如果右指针的字符存在于hashmap中，就减1
            if rightChar in hashmap:
                hashmap[rightChar] -= 1
#           记录之后右指针向右移动
            right += 1
#           检查窗口是否吧t中的字符全部覆盖了，全部覆盖了，那么窗口的左指针就要向右移动
            while check(hashmap):
#           如果现在的窗口比之前的小，就要更新窗口的长度和起始位置
                if right - left < windowLength:
                    windowLength = right - left
                    strStart = left
#               移除窗口中最左边的元素，缩小窗口
#               既然要把最左边的元素删了，那么就要把最左边的元素从hashmap中添加上，然后再去check(map)还是不是全覆盖了。
                leftChar = S[left]
#               如果在其中，那么下次一定会更新右指针了。
                if leftChar in hashmap:   
                    hashmap[leftChar] += 1
                left += 1
        if windowLength != len(S) + 1:
            return S[strStart:strStart + windowLength]
        return ""