Difficulty:: Hard
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).
Example:
1
2
| Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
|
Note:
- If there is no such window in S that covers all characters in T, return the empty string
"".
- If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
Solution
Language: Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
public String minWindow(String s, String t) {
if (s == null || s.length() == 0 || t == null || t.length() == 0) {
return "";
}
int[] targetMap = new int[256];
int[] sourceMap = new int[256];
for (int i = 0; i < t.length(); i++) {
targetMap[t.charAt(i)]++;
}
int min = Integer.MAX_VALUE;
String minString = "";
for (int i = 0, j = 0; i < s.length(); i++) {
while (j < s.length() && !isValid(sourceMap, targetMap)) {
sourceMap[s.charAt(j)]++;
j++;
}
if (min > j - i && isValid(sourceMap, targetMap)) {
minString = s.substring(i, j);
min = j - i;
}
sourceMap[s.charAt(i)]--;
}
return minString;
}
private boolean isValid(int[] source, int[] target) {
for (int i = 0; i < target.length; i++) {
if (target[i] > source[i]) {
return false;
}
}
return true;
}
}
|