forked from xiaoningning/java-algorithm-2010
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMinWindowSubString.java
More file actions
73 lines (57 loc) · 2.21 KB
/
MinWindowSubString.java
File metadata and controls
73 lines (57 loc) · 2.21 KB
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
* 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".
*/
public class MinWindowSubString {
public static void main(String[] args) {
String[] S = {"ADOBECODEBANC", "ABBADBABDRGBACCCB", "HBBHHCADBEBCAECBCCBB"};
String[] T = {"ABC", "ABBC", "ABBC"};
for (int i = 0; i < S.length; i++) {
String ret = minWindowSubString(S[i], T[i]);
System.out.println(ret);
}
}
public static String minWindowSubString(String source, String test) {
source.toUpperCase();
test.toUpperCase();
char[] sourceArray = source.toCharArray();
char[] testArray = test.toCharArray();
int sLen = source.length();
int tLen = test.length();
int minWindow = Integer.MAX_VALUE;
int minEnd = 0, minStart = 0;
int start = 0, end = 0, foundCounter = 0;
int[] needToFind = new int[256];
int[] hasFound = new int[256];
for (int i = 0; i < tLen; ++i)
needToFind[testArray[i]]++;
for (; end < sLen; end++) {
char endChar = sourceArray[end];
if (needToFind[endChar] == 0)
continue;
hasFound[endChar]++;
if (hasFound[endChar] <= needToFind[endChar])
foundCounter++;
if (foundCounter == tLen) { // found all
char startChar = sourceArray[start];
while (needToFind[startChar] == 0
|| hasFound[startChar] > needToFind[startChar]) {
if (hasFound[startChar] > needToFind[startChar])
hasFound[startChar]--;
start++;
startChar = sourceArray[start];
}
int currentWindow = end - start + 1;
if (currentWindow < minWindow) {
minWindow = currentWindow;
minEnd = end;
minStart = start;
}
}
}
return (foundCounter == tLen) ? source.substring(minStart, minEnd + 1) : "";
}
}