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

/*
 * @lc app=leetcode.cn id=76 lang=java
 *
 * [76] 最小覆盖子串
 *
 * https://leetcode-cn.com/problems/minimum-window-substring/description/
 *
 * algorithms
 * Hard (37.77%)
 * Likes:    565
 * Dislikes: 0
 * Total Accepted:    53.5K
 * Total Submissions: 141.8K
 * Testcase Example:  '"ADOBECODEBANC"\n"ABC"'
 *
 * 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
 * 
 * 示例：
 * 
 * 输入: S = "ADOBECODEBANC", T = "ABC"
 * 输出: "BANC"
 * 
 * 说明：
 * 
 * 
 * 如果 S 中不存这样的子串，则返回空字符串 ""。
 * 如果 S 中存在这样的子串，我们保证它是唯一的答案。
 * 
 * 
 */

// @lc code=start
class Solution {
    public String minWindow(String s, String t) {
        // 解法1：滑动窗口
        Map<Character,Integer> needs=new HashMap<>();
        Map<Character,Integer> window=new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char c=t.charAt(i);
            needs.put(c,needs.getOrDefault(c,0)+1);
        }

        int left=0,right=0;
        int start=0,minLen=Integer.MAX_VALUE;
        int match=0;

        while(right<s.length()){
            char c=s.charAt(right);
            if(needs.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if(window.get(c).equals(needs.get(c))){
                    match++;
                }
            }
            right++;

            while(match==needs.size()){
                char c2=s.charAt(left);
                if(right-left<minLen){
                    start=left;
                    minLen=right-left;
                }

                if(needs.containsKey(c2)){
                    window.put(c2,window.getOrDefault(c2,1)-1);
                    if(window.get(c2)<needs.get(c2)){
                        match--;
                    }
                }
                left++;
            }
        }
        return minLen==Integer.MAX_VALUE ? "" : s.substring(start,start+minLen);    
    }
}
// @lc code=end