Minimum Window Substring

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".

Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in s.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Example 2:

Input: s = "a", t = "a"
Output: "a"

Constraints:

• 1 <= s.length, t.length <= 105
• s and t consist of English letters.

分析：

看答案都看了很久才弄明白。

基本思路就是sliding window找到包含所有char的大string，然后开始从左往右减去多的char，直到找到minimum string为止。用一个hashmap来记住所有char出现的频率，一个counter来记录还需要多少个char。

在找到minimum string后，从minimum string的第二个char开始新的iteration，并在每个iteration最后update start 和 end 的值

class Solution(object):
 def minWindow(self, s, t):
 “””
 :type s: str
 :type t: str
 :rtype: str
 “””
 start, end = 0, 0
 need = collections.Counter(t)
 missing = len(t)
 i = 0
 for j, item in enumerate(s, 1):
   if need[item] > 0:
     missing -= 1
   need[item] -= 1
 
   if not missing:
     while i < j and need[s[i]] < 0:
       need[s[i]] += 1
       i += 1
 
     if not end or j — i <= end — start:
       start, end = i, j
 
     missing += 1
     need[s[i]] += 1
     i += 1
 
 return s[start:end]