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]