/
_0076_MinimumWindowSubstring.java
77 lines (71 loc) · 2.7 KB
/
_0076_MinimumWindowSubstring.java
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
package com.diguage.algorithm.leetcode;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
/**
* = 76. Minimum Window Substring
*
* https://leetcode.com/problems/minimum-window-substring/[Minimum Window Substring - LeetCode]
*
* @author D瓜哥, https://www.diguage.com/
* @since 2020-01-30 16:15
*/
public class _0076_MinimumWindowSubstring {
/**
* Runtime: 489 ms, faster than 5.03% of Java online submissions for Minimum Window Substring.
* Memory Usage: 322.8 MB, less than 5.32% of Java online submissions for Minimum Window Substring.
*
* ↓ 优化:在最后输出时,才截取字符串。
*
* Runtime: 33 ms, faster than 16.02% of Java online submissions for Minimum Window Substring.
* Memory Usage: 44.4 MB, less than 5.32% of Java online submissions for Minimum Window Substring.
*/
public String minWindow(String s, String t) {
if (Objects.isNull(s) || s.length() == 0
|| Objects.isNull(t) || t.length() == 0
|| s.length() < t.length()) {
return "";
}
Map<Character, Integer> needs = new HashMap<>(t.length());
for (char c : t.toCharArray()) {
needs.put(c, needs.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int minLength = Integer.MAX_VALUE;
int start = 0;
int match = 0;
Map<Character, Integer> windows = new HashMap<>(t.length());
while (right < s.length()) {
char rChar = s.charAt(right);
if (needs.containsKey(rChar)) {
int rCount = windows.getOrDefault(rChar, 0) + 1;
windows.put(rChar, rCount);
if (rCount == needs.get(rChar)) {
match++;
}
}
right++;
while (match == needs.size()) {
if (right - left < minLength) {
minLength = right - left;
start = left;
}
char lChar = s.charAt(left);
if (needs.containsKey(lChar)) {
int lCount = windows.get(lChar) - 1;
windows.put(lChar, lCount);
if (lCount < needs.get(lChar)) {
match--;
}
}
left++;
}
}
return minLength == Integer.MAX_VALUE ? "" : s.substring(start, start + minLength);
}
public static void main(String[] args) {
_0076_MinimumWindowSubstring solution = new _0076_MinimumWindowSubstring();
String r1 = solution.minWindow("ADOBECODEBANC", "ABC");
System.out.println("BANC".equals(r1) + " : " + r1);
}
}