leetcode [76] 最小覆盖子串

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：

如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

思路：滑动窗口，先找到第一个在目标串中的字符，然后往后搜索，直到涵盖所有目标字符。然后收缩左侧，直到第一个在目标串中的字符。注意，可能收缩后还是满足条件的，因此收缩判断是循环。

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(t) == 0 or len(s) == 0 or len(t) > len(s):
            return ''
        
        count = {}
        for tt in t:
            if tt not in count:
                count[tt] = 1
            else:
                count[tt] += 1
        
        result = ''
        left = 0
        while left < len(s) and s[left] not in count:
            left += 1
        if left == len(s):
            return ''
        for i in range(left, len(s)):
            if s[i] in count:
                count[s[i]] -= 1
            while sum(1 for v in count.values() if v > 0) == 0:
                if result == '' or len(result) > i - left + 1:
                    result = s[left: i + 1]
                count[s[left]] += 1
                for j in range(left + 1, i + 1):
                    if s[j] in count:
                        left = j
                        break
        
        return result