Poison

76. Minimum Window Substring

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
class Solution {
public String minWindow(String s, String t) {
int MAX = 100001; // 注意该值需要大于测试用例字符串最大长度

int startIndex = 0, endIndex = MAX;
int[] targetMap = new int[256];
int targetChars = 0;
for (int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
if (targetMap[c]++ == 0) {
targetChars++;
}
}

int[] windowMap = new int[256];
int matchChars = 0;
int i = 0;
for (int j = 0; j < s.length(); j++) {
// window: [i, j]
char c = s.charAt(j);
if (++windowMap[c] == targetMap[c]) {
matchChars++;
}

while (matchChars >= targetChars) {
// 注意需要在满足条件时收集
if (j - i < endIndex - startIndex) {
startIndex = i;
endIndex = j;
}

char leftmost = s.charAt(i);
if (windowMap[leftmost]-- == targetMap[leftmost]) {
matchChars--;
}
i++;
}
}

return endIndex == MAX ? "" : s.substring(startIndex, endIndex + 1);
}
}
Reference

76. Minimum Window Substring
剑指 Offer II 017. 含有所有字符的最短字符串