76.Minimum Window Substring
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).
For example,S="ADOBECODEBANC"
T="ABC"
Minimum window is"BANC".
Note:
If there is no such window in S that covers all characters in T, return the empty string"".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
Analysis
大体思路: 从左往右扫S, 直到T中字符全部出现。移动左index来减小subarray的长度。
Step 1: 先扫一遍T，把T所有的字符和出现的次数记录在map中
Step2: 从左到右扫S，直到T中的字符全部出现(并记录左边index), 全部出现的条件是map中所有元素的value <= 0;
2.1 update start/end index if it is necessary, move left index by one and update map
2.2 repeatedly move left index to the right so that it is one of chars in t, and its map value >=0\(确保左index是T中的字符,并且没有重复\)
Time complexity: n^2 * m (match function cost m);
方法2用count更好一些, 方法2不管左index在哪
My Solution
class Solution {
public String minWindow(String s, String t) {
HashMap<Character, Integer> map = new HashMap<>();
int minLength = Integer.MAX_VALUE;
int start=-1; int end=-1;
for (int i=0; i<t.length(); ++i) {
char c = t.charAt(i);
if (map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
int i=-1; int j=0;
while (j < s.length()) {
char temp = s.charAt(j);
if (map.containsKey(temp)) {
if (i == -1) {
i = j;
}
map.put(temp, map.get(temp)-1);
while (match(map)) {
if (j-i+1 < minLength) {
minLength = j-i+1;
start = i;
end = j;
}
map.put(s.charAt(i), map.get(s.charAt(i))+1);
i++;
while(i < j && (!map.containsKey(s.charAt(i)) || map.get(s.charAt(i)) < 0)) {
if (map.get(s.charAt(i)) != null && map.get(s.charAt(i)) < 0) {
map.put(s.charAt(i), map.get(s.charAt(i))+1);
}
i++;
}
}
}
j++;
}
if (start == -1) {
return "";
}
return s.substring(start, end+1);
}
private boolean match(HashMap<Character, Integer> map) {
for (Integer i : map.values()) {
if (i > 0) {
return false;
}
}
return true;
}
}
Solution 2
https://leetcode.com/problems/minimum-window-substring/discuss/26810/
Generally, there are following steps:
- create a hashmap for each character in t and count their frequency in t as the value of hashmap.
- Find the first window in S that contains T. But how? there the author uses the count.
- Checking from the leftmost index of the window and to see if it belongs to t. The reason we do so is that we want to shrink the size of the window. 3-1) If the character at leftmost index does not belong to t, we can directly remove this leftmost value and update our window(its minLeft and minLen value) 3-2) If the character indeed exists in t, we still remove it, but in the next step, we will increase the right pointer and expect the removed character. If find so, repeat step 3.
public String minWindow(String s, String t) {
HashMap<Character, Integer> map = new HashMap();
for(char c : t.toCharArray()){
if(map.containsKey(c)){
map.put(c, map.get(c)+1);
}
else{
map.put(c, 1);
}
}
int left = 0, minLeft=0, minLen =s.length()+1, count = 0;
for(int right = 0; right<s.length(); right++){
char r = s.charAt(right);
if(map.containsKey(r)){//the goal of this part is to get the first window that contains whole t
map.put(r, map.get(r)-1);
if(map.get(r) == 0) count++;//identify if the first window is found by counting frequency of the characters of t showing up in S
}
while(count == t.length()){//if the count is equal to the length of t, then we find such window
if(right-left+1 < minLen){//jsut update the minleft and minlen value
minLeft = left;
minLen = right-left+1;
}
char l = s.charAt(left);
if(map.containsKey(l)){//starting from the leftmost index of the window, we want to check if s[left] is in t. If so, we will remove it from the window, and increase 1 time on its counter in hashmap which means we will expect the same character later by shifting right index. At the same time, we need to reduce the size of the window due to the removal.
map.put(l, map.get(l)+1);
if(map.get(l)>0) count--;
}
left++;//if it doesn't exist in t, it is not supposed to be in the window, left++. If it does exist in t, the reason is stated as above. left++.
}
}
return minLen==s.length()+1?"":s.substring(minLeft, minLeft+minLen);
}
My Solution 2
public String minWindow(String s, String t) {
if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
return "";
}
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < t.length(); ++i) {
Integer n = map.get(t.charAt(i));
if (n == null) {
map.put(t.charAt(i), 1);
} else {
map.put(t.charAt(i), n + 1);
}
}
int ms = -1; int mf = s.length() - 1;
int slow = -1;
int count = map.size();
for (int fast = 0; fast < s.length(); ++fast) {
if (map.containsKey(s.charAt(fast))) {
if (slow == -1) {
slow = fast;
}
int n = map.get(s.charAt(fast));
map.put(s.charAt(fast), n - 1);
if (n - 1 == 0) {
count--;
}
}
while (count == 0) {
if (mf - ms > fast - slow) {
mf = fast;
ms = slow;
}
Integer n = map.get(s.charAt(slow));
map.put(s.charAt(slow), n + 1);
if (n == 0) {
count++;
}
slow++;
while (slow < fast && (!map.containsKey(s.charAt(slow)) || map.get(s.charAt(slow)) < 0)) {
Integer num = map.get(s.charAt(slow));
if (num != null) {
map.put(s.charAt(slow), num + 1);
}
slow++;
}
}
}
return ms == -1 ? "" : s.substring(ms, mf + 1);
}