76. 最小覆盖子串

题目链接

解题思路：以i开头，最小覆盖子串是什么，然后求出所有的结果，最小的便是。先求出i的结果，是[i, j]，然后求i+1时，直接从j后遍历即可。

• 窗口的思想，窗口在[i, j]，然后来到i+1，先把i弹出去，弹出去的前提是，s[i]是我们需要的字符。然后再看[i + 1, j]是否满足，如果不满足，右边界再继续扩。

代码

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        ans_begin = -1
        ans_end = -1
        ans_len = 1e+10
        char_count = {}    # 需要的字符
        need = 0
        for ch in t:
            if ch in char_count:
                char_count[ch] += 1
            else:
                char_count[ch] = 1
                need += 1
        j = 0
        for i in range(0, len(s), 1):
            # 先把i - 1弹出去
            if i > 0 and s[i - 1] in char_count: 
                char_count[s[i - 1]] += 1
                if char_count[s[i - 1]] == 1 :
                    need += 1
            while j < len(s) and need > 0:
                if s[j] in char_count:
                    char_count[s[j]] -=1
                    if char_count[s[j]] == 0:
                        need -=1
                j += 1
            # [i, j) 满足了条件
            if need == 0 and j - i < ans_len:
                ans_len = j - i
                ans_begin = i
                ans_end = j - 1
        return s[ans_begin : ans_end + 1]