class Solution {
public String minWindow(String s, String t) {
String ret = null;
Set<Character> charSet = t.chars().mapToObj(c -> (char) c)
.collect(Collectors.toSet());
List<Integer> indexList = new ArrayList<>();
Map<Character, Integer> need = new HashMap<>();
for (int i=0; i<s.length(); i++) {
Character c = s.charAt(i);
if (charSet.contains(c)) {
indexList.add(i);
}
}
for (int i=0; i<t.length(); i++) {
Character c = t.charAt(i);
need.put(c, need.getOrDefault(c, 0) + 1);
}
int j = 0;
for (int i=0; i<indexList.size(); i++) {
Character c1 = s.charAt(indexList.get(i));
need.put(c1, need.get(c1)-1);
if (need.get(c1) == 0) {
charSet.remove(c1);
}
Character c2 = s.charAt(indexList.get(j));
while (need.get(c2) < 0) {
need.put(c2, need.get(c2)+1);
j += 1;
c2 = s.charAt(indexList.get(j));
}
if (charSet.isEmpty() &&
(ret == null || (indexList.get(i) - indexList.get(j) + 1) < ret.length())) {
ret = s.substring(indexList.get(j), indexList.get(i)+1);
}
}
if (ret == null) return "";
return ret;
}
}