76. 最小覆盖子串

https://leetcode-cn.com/problems/minimum-window-substring/

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

示例:

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

说明:

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

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        left = right = 0
        start = 0
        match = 0
        min_len = float('inf')
        length_s = len(s)
        window = {}
        needs = {}

        for i in t:
            needs[i] = needs.get(i, 0) + 1

        while right < length_s:
            c = s[right]
            if c in needs:
                window[c] = window.get(c, 0) + 1
                if window[c] == needs[c]:
                    match += 1
            right += 1

            while len(needs) == match:
                if right - left < min_len:
                    start = left
                    min_len = right - left
                t = s[left]
                if t in needs:
                    window[t] -= 1
                    if window[t] < needs[t]:
                        match -= 1
                left += 1

        return '' if min_len == float('inf') else s[start:start+min_len]