Skip to content

Instantly share code, notes, and snippets.

@yanjinbin
Created December 22, 2019 11:02
Show Gist options
  • Save yanjinbin/3c0d53e97ceb7af7b18d1cde07c2968a to your computer and use it in GitHub Desktop.
Save yanjinbin/3c0d53e97ceb7af7b18d1cde07c2968a to your computer and use it in GitHub Desktop.
```java
public String minimumWindow01(String s, String t) {
int l = 0, r = 0, N = s.length() , start = 0, minLen = Integer.MAX_VALUE;
Map<Character, Integer> needs = new HashMap();
for (char c : t.toCharArray()) {
needs.put(c, needs.getOrDefault(c, 0) + 1);
}
Map<Character, Integer> windows = new HashMap();
int match = 0;
while (r < N) {
char c1 = s.charAt(r);
if (needs.containsKey(c1)) {
windows.put(c1, windows.getOrDefault(c1, 0) + 1);
if (windows.get(c1) == needs.get(c1)) {
match++;
}
}
r++;
// find 可行解, pursue 最优解
while (match == needs.size()) {
// update
if (r - l < minLen) {
start = l;
minLen = r - l;
}
char c2 = s.charAt(l);
if (needs.containsKey(c2)) {
windows.put(c2, windows.get(c2) - 1);
if (windows.get(c2) < needs.get(c2)) {
match--;
}
}
l++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
```
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment