LeetCode/MinimumWindowSubstring.java at master · Orio77/LeetCode · GitHub

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
importjava.util.HashMap;
importjava.util.HashSet;
importjava.util.Map;
importjava.util.Set;

classSolution {
publicStringminWindowMyApproach(Strings, Stringt) {
intsLength = s.length();
inttLength = t.length();
if (tLength > sLength || tLength == 0) {
return"";
 }
// Create 3 pointers
intone = 0;
inttwo = 0;
intthree = 0;
// Create the shortest sequence variable
intshortest = Integer.MAX_VALUE;
intsavedOne = 0;
intsavedThree = 0;
// Create the chars arrays
char[] sChars = s.toCharArray();
char[] tChars = t.toCharArray();
// Create set for t chars
Set<Character> tCharsSet = newHashSet<>();
for (inti = 0; i < tChars.length; i++) {
tCharsSet.add(tChars[i]);
 }
// Start looking for the sequence in a while loop
while (three < sLength) {
one = two;
two = three;
three++;
if (three == sLength) {
returns.substring(savedOne, savedThree);
 }

while (one < sLength) {
if (!tCharsSet.contains(sChars[one])) {
one++;
 }
 }
if (!tCharsSet.isEmpty() && tCharsSet.contains(sChars[one])) {
tCharsSet.remove(sChars[one]);
two = one;
 }

while (two < sLength) {
if (!tCharsSet.contains(sChars[two])) {
two++;
 }
 }
if (!tCharsSet.isEmpty() && tCharsSet.contains(sChars[two])) {
tCharsSet.remove(sChars[two]);
three = two;
 }

while (tCharsSet.isEmpty() && three < sLength) {
if (tCharsSet.contains(sChars[three])) {
tCharsSet.remove(sChars[three]);
 }
 }
if (!tCharsSet.isEmpty()) {
return"";
 }

if (three - one < shortest) {
savedOne = one;
savedThree = three;
 }
 }
// return shortest
returns.substring(savedOne, savedThree);
 }

publicStringminWindow(Strings, Stringt) {
if (s.length() < t.length()) {
returnnewString();
 }

Map<Character, Integer> map = newHashMap<>();
for (charc : t.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
 }

intcounter = map.size();
intstart = 0;
intend = 0;
inthead = 0;
intlen = Integer.MAX_VALUE;

while (end <s.length()) {
charc = s.charAt(end);
if (map.containsKey(c)) {
map.put(c, map.get(c) - 1);
if (map.get(c) == 0) {
counter --;
 }
 }

end++;
while (counter == 0) {
chartempc = s.charAt(start);
if (map.containsKey(tempc)) {
map.put(tempc, map.get(tempc) + 1);
if (map.get(tempc) > 0) {
counter++;
 }
 }
if (end - start < len) {
len = end - start;
head = start;
 }
start++;
 }
 }
if (len == Integer.MAX_VALUE) {
returnnewString();
 }
returns.substring(head, head + len);
 }
}