-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathminimum-window-substring.java
More file actions
66 lines (55 loc) · 1.64 KB
/
Copy pathminimum-window-substring.java
File metadata and controls
66 lines (55 loc) · 1.64 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
public class Solution {
private int[] target;
private boolean satisfy(int[] window) {
for (int i = 0; i < 256; i++) {
if (window[i] < target[i]) {
return false;
}
}
return true;
}
public String minWindow(String S, String T) {
if (S.length() == 0 || T.length() == 0) {
return "";
}
target = new int[256];
for (int i = 0; i < T.length(); i++) {
target[(int)T.charAt(i)]++;
}
int[] current = new int[256];
int head = 0;
int tail = 0;
int min = Integer.MAX_VALUE;
int bestHead = 0;
while (head <= tail && tail < S.length()) {
current[(int)S.charAt(tail)]++;
boolean moved = true;
while (moved && satisfy(current)) {
moved = false;
int length = tail - head + 1;
if (length < min) {
min = length;
bestHead = head;
}
if (head < tail) {
current[(int)S.charAt(head)]--;
head++;
moved = true;
}
for (; head < tail; head++) {
moved = true;
if (target[(int)S.charAt(head)] > 0) {
break;
}
current[(int)S.charAt(head)]--;
}
}
tail++;
}
if (min != Integer.MAX_VALUE) {
return S.substring(bestHead, bestHead + min);
} else {
return "";
}
}
}