题解 | #最小覆盖子串#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param S string字符串
     * @param T string字符串
     * @return string字符串
     */
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> cnt = new HashMap<>();
    public String minWindow (String S, String T) {
        // write code here
        int sizet = T.length();
        int sizes = S.length();
        if(sizet>sizes){
            return "";
        }
        for (int i = 0; i < sizet; i++) {
            need.put(T.charAt(i), need.getOrDefault(T.charAt(i), 0) + 1);
            cnt.put(S.charAt(i), cnt.getOrDefault(S.charAt(i), 0) + 1);
        }
        int start = 0;
        int end = sizet - 1;
        int length = Integer.MAX_VALUE;
        int result = 0;
        while (end < sizes&&start<=end) {
            if (check()) {
                if (end - start + 1 < length) {
                    length = end - start + 1;
                    result = start;
                }
                System.out.println("start:"+start+"end:"+end+"length:"+length);
                Integer count = cnt.getOrDefault(S.charAt(start), 0);
                if (count > 1) {
                    cnt.put(S.charAt(start), count - 1);

                } else {
                    cnt.remove(S.charAt(start));
                }
                start++;

            } else {
                ++end;
                if (end < sizes) {
                    cnt.put(S.charAt(end), cnt.getOrDefault(S.charAt(end), 0) + 1);
                }



            }


        }

        return length<Integer.MAX_VALUE? S.substring(result, result + length):"";
    }

    public boolean check() {
        for (Character c :    need.keySet()) {
            Integer needCount = need.get(c);
            Integer nowCount =  cnt.getOrDefault(c, 0);
            if (nowCount < needCount) {
                return false;
            }

        }
        return true;

    }
}