LeetCode-76、最小覆盖子串-困难

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

示例：

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

说明：

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

?

代码：

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or not s:
            return ''
        
        from collections import Counter
        dict_t = Counter(t)
        types = len(dict_t)

        left, right = 0, 0
        formed = 0
        dict_c = {}
        ans = (float('inf'), 0, 0)

        while right < len(s):
            char = s[right]
            dict_c[char] = dict_c.get(char, 0) + 1

            if char in dict_t and dict_c[char] == dict_t[char]:
                formed += 1

            while left <= right and formed == types:
                char = s[left]
                if right+1-left < ans[0]:
                    ans = (right+1-left, left, right)
                dict_c[char] -= 1
                if char in dict_t and dict_c[char] < dict_t[char]:
                    formed -= 1
                left += 1    
            right += 1    
        return '' if ans[0] == float('inf') else s[ans[1]:ans[2]+1]

?

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or not s:
            return ''
        
        from collections import Counter
        dict_t = Counter(t)
        types = len(dict_t)

        left, right = 0, 0
        formed = 0
        dict_c = {}
        ans = (float('inf'), 0, 0)

        while right < len(s):
            char = s[right]
            if char in dict_t:
                dict_c[char] = dict_c.get(char, 0) + 1
                if dict_c[char] == dict_t[char]:
                    formed += 1
            while left <= right and formed == types:
                while s[left] not in dict_t:
                    left += 1
                char = s[left]
                if right+1-left < ans[0]:
                    ans = (right+1-left, left, right)
                dict_c[char] -= 1
                if dict_c[char] < dict_t[char]:
                    formed -= 1
                left += 1    
            right += 1
        
        return '' if ans[0] == float('inf') else s[ans[1]:ans[2]+1]