最小覆盖子串

链接：https://www.nowcoder.com/questionTerminal/c466d480d20c4c7c9d322d12ca7955ac?f=discussion
来源：牛客网

[编程题]最小覆盖子串
热度指数：76918时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。

数据范围：
0≤∣S∣,∣T∣≤10000
0≤∣S∣,∣T∣≤10000，保证s和t字符串中仅包含大小写英文字母
要求：进阶：空间复杂度 O(n)O(n) ， 时间复杂度 O(n)O(n)
例如：
S="XDOYEZODEYXNZ"
T="XYZ"
找出的最短子串为

"YXNZ".

注意：
如果 s 中没有包含 t 中所有字符的子串，返回空字符串 “”；
满足条件的子串可能有很多，但是题目保证满足条件的最短的子串唯一。

示例1
输入

"XDOYEZODEYXNZ","XYZ"
输出

"YXNZ"
示例2
输入

"abcAbA","AA"
输出

"AbA"

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param S string字符串
     * @param T string字符串
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        HashMap hs = new HashMap<>();
        HashMap ht = new HashMap<>();
        String shortString = "";
        for (char c : T.toCharArray()) {
            ht.put(c, ht.getOrDefault(c, 0) + 1);
        }
        int count = 0;
        int len = 99999;
        for (int i = 0, j = 0; i < S.length(); i++) { // j head pos, i bottom pos
            hs.put(S.charAt(i), hs.getOrDefault(S.charAt(i), 0) + 1);
            if (ht.containsKey(S.charAt(i)) &&
ht.get(S.charAt(i)) >= hs.get(S.charAt(
                            i))) { // 找到ht中包含的字符， 且数量小于ht该字符的总数，代表需要计数
                count ++;
            }
            // 缩头。当头指针小于尾指针 且 ht中不含字符或小于该位置的字符的数量
while (i > j && (!ht.containsKey(S.charAt(j)) ||
                             ht.get(S.charAt(j)) < hs.get(S.charAt(j)))) {
                hs.put(S.charAt(j), hs.getOrDefault(S.charAt(j), 0) - 1);
                j++;
            }

            if (count == T.length() && i - j + 1 < len) {
                len = i - j + 1;
                shortString = S.substring(j, i + 1);
            }

        }
        return shortString;

    }
}