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.

Time: O(N)

class Solution: def minWindow(self, s: str, t: str) -> str: res = ‘‘ my_dict = {} for char in t: freq = my_dict.get(char, 0) my_dict[char] = freq + 1 count, start, end, min_len = len(my_dict), 0, 0, sys.maxsize res_end, res_start = 0, 0 while end != len(s): char = s[end] if char in my_dict: my_dict[char] -= 1 if my_dict[char] == 0: count -= 1 end += 1 while count == 0: start_char = s[start] if start_char in my_dict: my_dict[start_char] += 1 if my_dict[start_char] > 0: count += 1 if min_len > end - start: min_len = end - start res_end = end res_start = start start += 1 return s[res_start: res_end]