76. 最小覆盖子串(困难）-子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

分析

• 悟出两个道理，对于这类代码，甚至其他类型的代码，可以氛围两部分，一部分是正常遍历，另一部分就是变化的代码（这个是最难的）
• 分出这两部分好处就是，思考的时候可以分出更加具体化，写的时候可以全局考虑后，局部考虑，有点相当于列计划大纲一样
• 这里就是需要考虑的点比较多，比如设置左右边界，满足时刻所需要的变量等
• 什么时候算是窗口满足要求，这个感觉是最难得

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        
        # 设置t中的字母个数字典
        t_dict = {}
        for tt in t:
            if tt in t_dict:
                t_dict[tt] += 1
            else:
                t_dict[tt] = 1

        # 设置左右边界
        l, r = 0, 0

        # 满足时刻所需变量
        required_alpha_num = len(t_dict)
        formed_num = 0

        # 遍历常态
        n = len(s)
        window_dict = {}

        # 记录中间结果
        ans = float("inf"), None, None
        while r < n:
            # 遍历常态
            charater = s[r]
            if charater in window_dict:
                window_dict[charater] += 1
            else:
                window_dict[charater] = 1

            # 变化1
            if charater in t_dict and window_dict[charater] == t_dict[charater]:
                formed_num += 1
            
            # 变化2，这时候另一个循环，也就是左边边界缩进的循环
            while l <= r and formed_num == required_alpha_num:
                
                # 遍历常态
                charater = s[l]
                window_dict[charater] -= 1
                # 变化21
                if r-l + 1< ans[0]:
                    ans = (r -l + 1, l, r)
                # 变化22
                if charater in t_dict and window_dict[charater] < t_dict[charater]:
                    formed_num -= 1
                
                l += 1
            r += 1
        
        return "" if ans[0] == float("inf") else s[ans[1]: ans[-1] + 1]