動機

現在寫sliding window的風格跟以前完全不一樣

Problem

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string .

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

 

Example 1:

Input: s = ADOBECODEBANC, t = ABCOutput: BANCExplanation: The minimum window substring BANC includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = a, t = aOutput: aExplanation: The entire string s is the minimum window.

Example 3:

Input: s = a, t = aaOutput: Explanation: Both 'a's from t must be included in the window.Since the largest window of s only has one 'a', return empty string.

 

Constraints:

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 105
  • s and t consist of uppercase and lowercase English letters.

 

Follow up: Could you find an algorithm that runs in O(m + n) time?

Sol

先看之前寫的再看別人寫的

一路長到合法，紀錄，縮一格

但因為檢查合法的方式是dict比對，所以超慢

def lt(a,b):
    return any([a.get(k,0) < b[k] for k in b.keys()])
def gt_or_eq(a,b):
    return all([a.get(k,0) >= b[k] for k in b.keys()])
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        a,b,seen,t = 0,0, Counter(), Counter(t)
        x,y = -1,-1
        while a < len(s):
            while b < len(s) and lt(seen,t):
                if s[b] in t:
                    seen.update(s[b])
                b += 1
            #print("expand",a,b,s[a:b])
            while a < b:
                if s[a] not in t:
                    a += 1
                elif seen[s[a]]-1 >= t[s[a]]:
                    seen.subtract(s[a])
                    a += 1
                else:
                    break
            #print("shrink",a,b,s[a:b])
            updateXY, legal = (x == -1 or b-a < y-x), gt_or_eq(seen,t)
            # 做array操作之前要把前提檢查一遍
            x,y = (a,b) if updateXY and legal else (x,y)
            if a < len(s):
                seen.subtract(s[a])
            a+=1
        return s[x:y]

看別人寫的，用t的counter去扣，如果不在t中就會是負的，之後就是用一個cnt去看，有多少char已經收集好了，等到了，就可以用window的index求len

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        dict_t_cnt = Counter(t)     
        
        left = right = cnt = 0  # cnt control the valid charater in the window
        minlen = float('inf')
        res = ""
        
        # the window is build upon the string s
        for right in range(len(s)):
            dict_t_cnt[s[right]] -= 1
            if dict_t_cnt[s[right]] >= 0: cnt += 1  # if it is less than zero, means the window has enough charater s[right]
                
            while cnt == len(t): 
                if minlen > right - left  + 1: 
                    minlen =  right - left  + 1
                    res = s[left : right + 1]
                
                dict_t_cnt[s[left]] += 1
                if dict_t_cnt[s[left]] > 0: cnt -= 1
                left += 1
                
        return res

現在的風格

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        cs = set(t)
        limit = Counter(t)
        win = defaultdict(int)
        i,ret = 0,float('inf')
        ans = ""
        for j,c in enumerate(s):
            win[c] += 1

            while i<=j and all([win[x] >= limit[x] for x in cs]):
                if ret > j-i+1:
                    ret, ans = j-i+1, s[i:j+1]
                win[s[i]] -= 1
                i += 1
        return ans