/**
1. 找出s的一个子串是t的最小覆盖集
1.1 -> 判断一个字符串str包含t的所有字符
1.2 -> 让str最小
2. 怎么维护当前字符串包含t?
2.1 先预处理t, 记录一共有total个字符, 并且用map记录每个字符的个数
2.2 遍历字符串str, 如果在map中, map[char]--, 如果 map[char] == 0, 说明该字符完全包含, count++,
2.3 如果最后 count == total 那么str完全包含t的所有字符
3. 怎么让str最小?
3.1 指针i每次向右扩展一位, 并更新map
3.2 指针j在满足完全覆盖的情况下向右扩展, 向右收缩边界到最小, 同时更新map
3.3 如果满足完全覆盖, 更新结果集l, r
4. 参照: https://www.acwing.com/solution/LeetCode/content/160/
*/
class Solution {
public String minWindow(String s, String t) {
if (s.length() == 0 || t.length() == 0) return "";
Map<Character, Integer> pattern = new HashMap<>();
int l = 0, r = Integer.MAX_VALUE, total = 0;
for (int i = 0 ; i < t.length() ; i ++){
char c = t.charAt(i);
if (pattern.get(c) == null) {
pattern.put(c, 0);
total++;
}
pattern.put(c, pattern.get(c) + 1);
}
char[] str = s.toCharArray();
for (int i = 0, j = 0, count = 0; i < str.length; i ++){
if (pattern.get(str[i]) == null) continue;
pattern.put(str[i], pattern.get(str[i]) - 1);
if (pattern.get(str[i]) == 0) count ++ ;
if (count != total) continue;
for ( ; ; j++){
if (pattern.get(str[j]) == null) continue;
if (pattern.get(str[j]) >= 0) break;
pattern.put(str[j], pattern.get(str[j]) + 1);
}
if (i - j < r - l || r == Integer.MAX_VALUE){
r = i;
l = j;
}
}
return r == Integer.MAX_VALUE ? "": s.substring(l, r+1);
}
}