题解 | 最小覆盖子串

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param S string字符串
     * @param T string字符串
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        Map<Character, Integer> matchMap = new HashMap<Character, Integer>();

        for (int i = 0; i < T.length(); i++) {
            char c = T.charAt(i);
            matchMap.put(c, matchMap.getOrDefault(c, 0) + 1);
        }
        int left = 0;
        int right = 0;
        int min = S.length();
        String str = "";
        while (right < S.length() || left < right) {
            if (isMatch(map, matchMap)) {
                if (min >= right - left) {
                    min = right - left;
                    str = S.substring(left, Math.min(right, S.length()));
                }
                map.put(S.charAt(left), map.getOrDefault(S.charAt(left), 0) - 1);
                left++;
            } else {
                if (right > S.length() - 1) {
                    break;
                }
                map.put(S.charAt(right), map.getOrDefault(S.charAt(right), 0) + 1);
                right++;
            }
        }
        return str;
    }

    static boolean isMatch(Map<Character, Integer> map,
                           Map<Character, Integer> matchMap) {
        for (Character key : matchMap.keySet()) {
            Integer i = matchMap.get(key);
            Integer orDefault = map.getOrDefault(key, 0);
            if (i > orDefault) {
                return false;
            }
        }
        return true;
    }
}