-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathminimumWindowSubstring.java
More file actions
108 lines (89 loc) · 3.12 KB
/
minimumWindowSubstring.java
File metadata and controls
108 lines (89 loc) · 3.12 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
98
99
100
101
102
103
104
105
106
107
108
public class Solution {
public String minWindow(String S, String T) {
// Start typing your Java solution below
// DO NOT write main() function
if(S.length() == 0 || T.length() == 0 || S.length() < T.length()) return "";
int start = S.length() - 1;
int len = -1;
HashMap<Character, Integer> target = new HashMap();
HashMap<Character, Integer> map = new HashMap();
for(int i = 0; i < T.length(); ++i) {
char c = T.charAt(i);
if(!target.containsKey(c)) {
target.put(c, 1);
map.put(c, 0);
} else {
int count = target.get(c);
target.put(c, count + 1);
}
}
HashMap<Character, Integer> copy = new HashMap(target);
int left = S.length() - 1;
for(int i = S.length() - 1; i >= 0; --i) {
char c = S.charAt(i);
if(!target.containsKey(c)) {
continue;
}
if(map.containsKey(c)) {
int count = map.get(c) + 1;
map.put(c, count);
} else {
map.put(c, 1);
}
if(copy.containsKey(c)) {
int count = copy.get(c) - 1;
copy.put(c, count);
if(count == 0) copy.remove(c);
if(copy.size() == 0) {
start = i;
left = i - 1;
len = S.length() - i;
break;
}
}
}
if(len == -1) return "";
if(T.length() < 2) {
return T;
}
int curlen = len;
for(int i = S.length() - 2; i >= T.length() - 1; --i) {
char c = S.charAt(i + 1);
if(!target.containsKey(c)) {
--curlen;
if(curlen < len) {
len = curlen;
start = left + 1;
}
continue;
}
int count = map.get(c);
if(count > target.get(c)) {
map.put(c, count - 1);
--curlen;
if(curlen < len) {
len = curlen;
start = left + 1;
}
} else {
while(left >= 0) {
char ch = S.charAt(left);
if(target.containsKey(ch) && ch != c) {
int cnt = map.get(ch) + 1;
map.put(ch, cnt);
}
if(ch == c) break;
--left;
}
if(left < 0) break;
--left;
curlen = i - left;
if(curlen < len) {
len = curlen;
start = left + 1;
}
}
}
return S.substring(start, start + len);
}
}