Description

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:

If there is no such window in S that covers all characters in T, return the empty string "".
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

Solution

思路，使用双指针left记录start, right 记录cover 的end
（思路好像，代码异常难写）

class Solution:
    def build_dict(self,t):
        res ={}
        for c in list(t):
            if c in res:
                res[c] +=1
            else:
                res[c] = 1
        return res
    def minWindow(self, s: str, t: str) -> str:
        if len(s)< len(t):
            return ""
        c_dict = self.build_dict(t) # char needed for template
        start = 0
        char_cnt = 0
        min_len = 1e6
        idx = 0
        s = list(s)
        for end in range(len(s)):
            if s[end] in c_dict:
                c_dict[s[end]]-=1
                if c_dict[s[end]]==0:  ##注意条件
                    char_cnt +=1
            else:
                continue
            # check if substr covered the template
            while char_cnt == len(c_dict):   #注意条件
                if min_len > end-start +1:
                    min_len = end-start +1
                    idx = start
                # move forward for start point        
                ch = s[start]
                start+=1  #注意更新
                if ch not in c_dict:
                    continue
                c_dict[ch]+=1
                if c_dict[ch] >0:
                    char_cnt -= 1
        if min_len == 1e6:
            return ""
        return "".join(s[idx:idx+min_len])