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]
class Solution {
public String minWindow(String s, String t) {
Map<Character, Integer> map = new HashMap<>();
int minLen = Integer.MAX_VALUE;
char[] tCharArray = t.toCharArray();
for (char c : tCharArray) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
int count = map.size(), start = 0, globStart = 0, i = 0;
char[] sCharArray = s.toCharArray();
while (i < sCharArray.length) {
char cur = sCharArray[i];
if (map.containsKey(cur)) {
map.put(cur, map.get(cur) - 1);
if (map.get(cur) == 0) {
count -= 1;
}
}
i += 1;
while (count == 0) {
char sChar = sCharArray[start];
if (map.containsKey(sChar)) {
map.put(sChar, map.get(sChar) + 1);
if (map.get(sChar) > 0) {
count += 1;
}
}
if (i - start < minLen) {
globStart = start;
minLen = i - start;
}
start += 1;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(globStart, globStart + minLen);
}
}