Idea is simple. Using a hashmap to store the number of elements in T.
Scan S by using two pointers.
public String minWindow(String S, String T) {
if (S==null || S.length()==0) return "";
//Put all the elements in the hashmap
Map<Character, Integer> map = new HashMap<>();
for (int i=0; i<T.length(); i++) {
if (map.containsKey(T.charAt(i))) {
map.put(T.charAt(i), map.get(T.charAt(i))+1);
} else {
map.put(T.charAt(i), 1);
}
}
//Scan the String S
int left = 0, right = 0, count = 0, minStart = 0, minLen = S.length()+1; //Initial value is larger than S
for (; right<S.length(); right++) {
if (map.containsKey(S.charAt(right))) {
map.put(S.charAt(right), map.get(S.charAt(right))-1);
if (map.get(S.charAt(right))>= 0) {
count++;
}
while (count == T.length()) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minStart = left;
}
if (map.containsKey(S.charAt(left))) {
map.put(S.charAt(left), map.get(S.charAt(left))+1);
if (map.get(S.charAt(left))>0) {
count--;
}
}
left++;
}
}
}
//Special case: could not find the T
if (minLen > S.length()) {
return "";
}
return S.substring(minStart, minStart+minLen);
}
No comments:
Post a Comment