Problem:
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".
Java Code:
public class Solution {
public String minWindow(String S, String T) {
String result = "";
if (S == null || S.length() == 0 || T == null || T.length() == 0) {
return result;
}
Map<Character, Integer> toFind = new HashMap<Character, Integer>();
for (int i = 0; i < T.length(); i++) {
if (toFind.containsKey(T.charAt(i))) {
toFind.put(T.charAt(i), toFind.get(T.charAt(i)) + 1);
} else {
toFind.put(T.charAt(i), 1);
}
}
Map<Character, Integer> found = new HashMap<Character, Integer>();
int tCount = 0;
int leftBound = 0;
for (int i = 0; i < S.length(); i++) {
char current = S.charAt(i);
if (!toFind.containsKey(current)) {
continue;
}
if (found.containsKey(current)) {
found.put(current, found.get(current) + 1);
} else {
found.put(current, 1);
}
if (found.get(current) <= toFind.get(current)) {
tCount++;
}
if (tCount == T.length()) {
while (leftBound < S.length()) {
char current2 = S.charAt(leftBound);
if (!toFind.containsKey(current2)) {
leftBound++;
continue;
}
if (found.get(current2) > toFind.get(current2)) {
leftBound++;
found.put(current2, found.get(current2) - 1);
continue;
}
break;
}
if (result.equals("") || S.substring(leftBound, i + 1).length() < result.length()) {
result = S.substring(leftBound, i + 1);
}
}
}
return result;
}
}
没有评论:
发表评论