package Code;

import java.util.HashMap;
import java.util.Map;

public class Code76 {
    static String minWindow(String s, String t){
        int m = s.length(), n = t.length();
        if(s == null || t==null || m< n){
            return "";
        }
        Map<Character, Integer> map = new HashMap<>();
        for(char c: t.toCharArray()){
            map.put(c, map.getOrDefault(c,0)+1);
        }
        Map<Character,Integer> win= new HashMap<>();
        int matched = 0;
        int l = 0, r = 0;
        int start = 0, minLen = Integer.MAX_VALUE;
        while(r < m){
            char c = s.charAt(r);
            win.put(c, win.getOrDefault(c,0)+1);
            //  // 如果窗口内该字符的频率等于 t 中该字符的频率
            if(map.containsKey(c) && win.get(c).equals(map.get(c))){
                matched++;
            }
            // 当窗口包含了 t 的所有字符时，尝试缩小窗口
            while(l <= r && matched == map.size()){
                if(r -l +1 < minLen){
                    start = l;
                    minLen = r - l +1;

                }
                // 移除左指针指向的字符
                char leftChar = s.charAt(l);
                win.put(leftChar, win.get(leftChar)-1);
                // 如果移除后窗口内该字符的频率小于 t 中该字符的频率
                if(map.containsKey(leftChar) && win.get(leftChar).intValue()< map.get(leftChar).intValue()){
                    matched--;
                }
                l++;
            }
            r++;
        }
        return minLen == Integer.MAX_VALUE? "": s.substring(start, start+minLen);


    }
    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC","ABC"));
    }
}