// @Title: 最小覆盖子串 (Minimum Window Substring)
// @Author: qisiii
// @Date: 2024-09-11 19:20:28
// @Runtime: 294 ms
// @Memory: 44.8 MB
// @comment: 
// @flag: 
class Solution {
    public String minWindow(String s, String t) {
        char[] tArray = t.toCharArray();
        char[] sArray = s.toCharArray();
        HashMap<Character, Integer> tMap = new HashMap<>();
        for (Character c : tArray) {
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }
        int start = 0, end = 0, len = s.length(), minStart = 0;
        boolean flag=false;
        HashMap<Character, Integer> sMap = new HashMap<>();
        while (end < s.length()) {
            sMap.put(sArray[end], sMap.getOrDefault(sArray[end], 0) + 1);
            while (check(tMap, sMap)) {
                flag=true;
                sMap.put(sArray[start], sMap.getOrDefault(sArray[start], 0) - 1);
                if ((end - start + 1) < len) {
                    len = end - start + 1;
                    minStart = start;
                }

                start++;
            }
            end++;
        }

        return flag?s.substring(minStart, minStart + len):"";
    }

    static boolean check(HashMap<Character, Integer> map1, HashMap<Character, Integer> map2) {
        for (Character key : map1.keySet()) {
            if (!map2.containsKey(key)) {
                return false;
            }
            if (map2.get(key)<map1.get(key)) {
                return false;
            }
        }
        return true;
    }
}