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**.
Example 1: Input: s = “ADOBECODEBANC”, t = “ABC” Output: “BANC” Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t. Example 2: Input: s = “a”, t = “a” Output: “a” Explanation: The entire string s is the minimum window. Example 3: Input: s = “a”, t = “aa” Output: "" 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?
- code
class Solution {
public String minWindow(String s, String t) {
if (s.length() < t.length()) return "";
int minLen = Integer.MAX_VALUE;
int l = 0, r = 0; //window
String res = s;
Map<Character, Integer> targetCount = new HashMap<>();
for (Character c: t.toCharArray()){
targetCount.put(c, targetCount.getOrDefault(c, 0) + 1);
}
Map<Character, Integer> curCount = new HashMap<>();
while (l <= r && r < s.length()){
curCount.put(s.charAt(r), curCount.getOrDefault(s.charAt(r), 0) + 1);
if (enoughCount(targetCount, curCount)){
// while left char not in target or is more than need, left++
while(l <= r && enoughCount(targetCount, curCount)){
curCount.put(s.charAt(l), curCount.get(s.charAt(l)) - 1);
l++;
}
String tempRes = s.substring(l-1, r+1); // one more l++ in while loop above
if (tempRes.length() < res.length()) res = tempRes;
minLen = res.length();
}
r++;
}
return minLen == Integer.MAX_VALUE ? "": res;
}
public boolean enoughCount(Map<Character, Integer> target, Map<Character, Integer> cur){
for (Character c: target.keySet()){
if (cur.getOrDefault(c, 0) < target.getOrDefault(c, 0)) return false;
}
return true;
}
}
- code
class Solution {
public String minWindow(String s, String t) {
int m = s.length(), n = t.length();
if(n > m || n == 0 || m == 0) return "";
int[] map = new int[128];
int left = 0, right =0, minLen = Integer.MAX_VALUE, startIndex = 0;
for(char ch: t.toCharArray()){
map[ch]++;
}
char[] chs = s.toCharArray();
while(right < m){
if(map[chs[right++]]-- > 0){
n--;
}
while(n ==0){
if(right-left < minLen){
startIndex = left;
minLen = right-left;
}
if(map[chs[left++]]++ == 0){
n++;
}
}
}
return minLen == Integer.MAX_VALUE ? "": new String(chs, startIndex, minLen);
}
}
- code store range as res
class Solution:
def minWindow(self, s, t):
dict_t = Counter(t)
target = sum(dict_t.values())
count = 0
l = 0
res = (0, inf)
for r in range(len(s)):
if s[r] in dict_t:
if dict_t[s[r]] > 0:
count += 1
dict_t[s[r]] -= 1
while count == target:
if r - l < res[1] - res[0]:
res = (l, r)
if s[l] in dict_t:
if dict_t[s[l]] == 0:
count -= 1
dict_t[s[l]] += 1
l += 1
return "" if res[1] == inf else s[res[0]:res[1]+1]