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.
Solution: 类似于All anagrams。因为window长度不定,所以用2指针。j一直增加,直到match == hashmap.size(),更新min和start和end,然后i++,并更新hashmap,直到不match。
public String minWindow(String s, String t) {
if (s.length() < t.length() || t.length() == 0 || s.length() == 0) {
return "";
}
Map<Character, Integer> hashmap = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
hashmap.put(c, hashmap.getOrDefault(c, 0) + 1);
}
int i = 0, j = 0, match = 0, min = Integer.MAX_VALUE, start = -1, end = -1;
while (j < s.length()) {
//要用while而不是if continue,因为有可能j == s.length()时match了
while (j < s.length() && match < hashmap.size()) {
char c = s.charAt(j);
Integer count = hashmap.get(c);
if (count != null) {
hashmap.put(c, count - 1);
//count从1变为0时,说明个数凑满,match++
if (count == 1) {
match++;
}
}
j++;
}
while (match == hashmap.size()) {
if (j - i < min) {
min = j - i;
start = i;
end = j;
}
char c = s.charAt(i);
Integer count = hashmap.get(c);
if (count != null) {
hashmap.put(c, count + 1);
//count从0变为1时,说明个数从凑满变为缺一个,match--
if (count == 0) {
match--;
}
}
i++;
}
}
if (start == -1) {
return "";
}
return s.substring(start, end);
}