forked from kdn251/interviews
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathminimumWindowSubstring.java
More file actions
87 lines (50 loc) · 2.14 KB
/
Copy pathminimumWindowSubstring.java
File metadata and controls
87 lines (50 loc) · 2.14 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
// 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 empty string "".
// If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
public class Solution {
public String minWindow(String s, String t) {
HashMap<Character, Integer> map = new HashMap<>();
for(char c : s.toCharArray()) {
map.put(c, 0);
}
for(char c : t.toCharArray()) {
if(map.containsKey(c)) {
map.put(c, map.get(c)+ 1);
}
else {
return "";
}
}
int start = 0;
int end = 0;
int minStart = 0;
int minLength = Integer.MAX_VALUE;
int counter = t.length();
while(end < s.length()) {
char c1 = s.charAt(end);
if(map.get(c1) > 0) {
counter--;
}
map.put(c1, map.get(c1) - 1);
end++;
while(counter == 0) {
if(minLength > end - start) {
minLength = end - start;
minStart = start;
}
char c2 = s.charAt(start);
map.put(c2, map.get(c2) + 1);
if(map.get(c2) > 0) {
counter++;
}
start++;
}
}
return minLength == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLength);
}
}