class Solution {
public String minWindow(String s, String t) {
if (s.length() == 0 || t.length() == 0) {
return "";
}
Map<Character, Integer> dictT = new HashMap<Character, Integer>();
for (int i = 0; i < t.length(); i++) {
int count = dictT.getOrDefault(t.charAt(i), 0);
dictT.put(t.charAt(i), count + 1);
}
int required = dictT.size();
List<Pair<Integer, Character>> filteredS = new ArrayList<Pair<Integer, Character>>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (dictT.containsKey(c)) {
filteredS.add(new Pair<Integer, Character>(i, c));
}
}
int l = 0, r = 0, formed = 0;
Map<Character, Integer> windowCounts = new HashMap<Character, Integer>();
int[] ans = {-1, 0, 0};
while (r < filteredS.size()) {
char c = filteredS.get(r).getValue();
int count = windowCounts.getOrDefault(c, 0);
windowCounts.put(c, count + 1);
if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
formed++;
}
while (l <= r && formed == required) {
c = filteredS.get(l).getValue();
int end = filteredS.get(r).getKey();
int start = filteredS.get(l).getKey();
if (ans[0] == -1 || end - start + 1 < ans[0]) {
ans[0] = end - start + 1;
ans[1] = start;
ans[2] = end;
}
windowCounts.put(c, windowCounts.get(c) - 1);
if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {
formed--;
}
l++;
}
r++;
}
return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
}
}
Runtime: 17 ms, faster than 25.92% of Java online submissions for Minimum Window Substring.
Memory Usage: 44.5 MB, less than 7.10% of Java online submissions for Minimum Window Substring.