-
Notifications
You must be signed in to change notification settings - Fork 17
Expand file tree
/
Copy pathSolution.java
More file actions
83 lines (75 loc) · 2.3 KB
/
Solution.java
File metadata and controls
83 lines (75 loc) · 2.3 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
package MinimumWindowSubstring;
import java.util.HashMap;
import java.util.Map;
/**
* User: Danyang
* Date: 1/28/2015
* Time: 15:42
*
* 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 {
/**
* Expand and shrink window
* Notice:
* 1. T can have duplicated
* @param S
* @param T
* @return
*/
public String minWindow(String S, String T) {
Map<Character, Integer> current = new HashMap<>();
Map<Character, Integer> required = new HashMap<>();
for(char c: T.toCharArray()) {
current.put(c, 0);
if(!required.containsKey(c))
required.put(c, 0);
required.put(c, required.get(c)+1);
}
int min_s = -1;
int min_e = S.length();
int i = 0;
int j = 0;
while(i<S.length() && j<S.length()+1) {
if(!foundAll(current, required)) {
if(j<S.length() && current.containsKey(S.charAt(j))) {
current.put(S.charAt(j), current.get(S.charAt(j))+1);
}
j++;
}
else {
if(min_e-min_s>j-i) {
min_s = i;
min_e = j;
}
if(current.containsKey(S.charAt(i))) {
current.put(S.charAt(i), current.get(S.charAt(i))-1);
}
i++;
}
}
if(min_s!=-1)
return S.substring(min_s, min_e);
else
return "";
}
boolean foundAll(Map<Character, Integer> cur, Map<Character, Integer> required) {
for(Map.Entry<Character, Integer> e: cur.entrySet()) {
if(e.getValue()<required.get(e.getKey()))
return false;
}
return true;
}
public static void main(String[] args) {
String ret = new Solution().minWindow("a", "aa");
System.out.println(ret);
}
}