forked from walnutown/CodingInTheDeep
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMinimumWindowSubstring.java
More file actions
98 lines (90 loc) · 3.13 KB
/
Copy pathMinimumWindowSubstring.java
File metadata and controls
98 lines (90 loc) · 3.13 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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/*
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 emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
*/
// Sliding Window
// Maintain two arrays to record the occurrences of needed characters and found characters
// Traverse the String S, update the occurrence arrays and the number of remaining chars that need to be found.
// When all needed chars haven been found, right shift the start index of window if possible,
// and update the min window.
// time: O(n); space: O(n), each char is accessed at most twice
public class Solution {
public String minWindow(String S, String T) {
if (S==null || T==null)
return "";
int M = S.length(), N = T.length();
if (M<N)
return "";
int[] need = new int[256], find = new int[256];
for (int i=0; i<N; i++)
need[(int)T.charAt(i)]++;
int start = 0, minStart = -1, minEnd = M; // make sure the initial value of minEnd-minStart is big enough
for (int i=0; i<M; i++){
int ch = (int) S.charAt(i);
if (find[ch]<need[ch])
N--;
find[ch]++;
if (N==0){
start = getStartIndex(need, find, S, start);
if (i-start<minEnd-minStart){
minEnd = i; minStart = start;
}
}
}
return minStart==-1?"": S.substring(minStart, minEnd+1);
}
private int getStartIndex(int[] need, int[] find, String S, int i){
for (; i<S.length(); i++){
int ch = (int) S.charAt(i);
if (find[ch]>need[ch])
find[ch]--;
else
break;
}
return i;
}
}
// TLE, use a string to store min window, easy for update
public class Solution {
public String minWindow(String S, String T) {
if (S==null || T==null)
return "";
int M = S.length(), N = T.length();
if (M<N)
return "";
int[] need = new int[256], find = new int[256];
for (int i=0; i<N; i++)
need[(int)T.charAt(i)]++;
String min = "";
int i = 0;
for (int j=0; j<M; j++){
int ch = (int) S.charAt(j);
if (find[ch]<need[ch])
N--;
find[ch]++;
if (N==0){
i = getStartIndex(need, find, S, i);
String s = S.substring(i, j+1);
if (min.equals("") || min.length()<s.length())
min = s;
}
}
return min;
}
private int getStartIndex(int[] need, int[] find, String S, int i){
for (; i<S.length(); i++){
int ch = (int) S.charAt(i);
if (find[ch]>need[ch])
find[ch]--;
else
break;
}
return i;
}
}