【数组&双指针】LeetCode 76. 最小覆盖子串【困难】

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = dict() # 用hash表need记录目标串中每一个字符的个数
        window = dict() # 用hash表window记录当前窗口中，包含的目标字符的个数
        # 用need记录所有目标字符的个数; 开始遍历目标字符串
        for _char in t:
            if _char not in need:
                # 若目标字符串中的字符不在need中，那么need与window均将该字符数目记录为0
                need[_char] = 0 
                window[_char] = 0
            need[_char] += 1 # 跳出if条件语句，需要将遍历到的char在need中进行+1记录
        left, right = 0, 0 # 用双指针遍历源字符串
        valid = 0 # 记录窗口中目标字符的每一类字符是否个数已经满足，满足就加1
        start = 0 # 记录窗口的右侧位置
        length = len(s) + 1 # 将窗口长度初始化为一个无效值，即大于源字符串的长度值
        # 右指针遍历字符串的每一个位置：作为窗口右侧结束位置
        while right < len(s):
            right_char = s[right]
            right += 1 # 增大窗口
            if right_char in need:
                # 若窗口内的最后一个字符在目标字符串中, 更新窗口中的字符个数
                window[right_char] += 1
                if need[right_char] == window[right_char]:
                    # 当前字符在窗口中的字符个数与目标字符串的字符个数相等，更新有效长度
                    valid += 1
            # 当窗口中的每一类字符个数都与目标串中的每一类字符个数相等，就不断缩小左侧指针
            while valid == len(need):
                # 更新最小的窗口长度
                if right - left < length:
                    start = left
                    length = right - left
                first_char = s[left]
                left += 1 # 缩小窗口

                # 若左侧字符在目标字符里面
                if first_char in need:
                    # 当前字符在窗口中的个数，与目标串个数相等，就减少有效长度
                    if window[first_char] == need[first_char]:
                        valid -= 1
                    # 更新窗口中的字符个数
                    window[first_char] -= 1
        return "" if length == len(s) + 1 else s[start:start + length]