# 0076. Minimum Window Substring
###### tags: `Leetcode` `Hard` `FaceBook` `Sliding Window`
Link: https://leetcode.com/problems/minimum-window-substring/
## 思路
用一个map记录t里面每个字符出现的次数，再用一个变量记录t里面一共有几个字符
在用sliding window的时候用一个map记录每个在t里面出现的字符出现的次数，如果一个字符在这个map中的count = tDict里面的count，就说明这个字符已经被满足了，那么formed就加1
如果formed==required，就说明t里面的所有字符都被满足了，这时可以移动左边指针，这里比较特别的一点是**每次移动左指针都要记录一次答案**，因为每次移动左指针剩的字符串都可能是有效的
**如果第20行```tDict.get(c).equals(winCnt.get(c))```写成```tDict.get(c)==winCnt.get(c)```就会错，Object和Object的比较最好还是用equals()，不要偷懒**
## Code

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> tDict = new HashMap<>();
        for(int i = 0;i < t.length();i++){
            tDict.put(t.charAt(i), tDict.getOrDefault(t.charAt(i),0)+1);
        }
        int required = tDict.size();
        
        Map<Character, Integer> winCnt = new HashMap<>();
        int l = 0;
        int r = 0;
        int formed = 0;
        int[] ans = new int[3];
        ans[0] = -1;
        ans[2] = Integer.MAX_VALUE;
        while(r < s.length()){
            char c = s.charAt(r);
            if(tDict.containsKey(c)){
                winCnt.put(c, winCnt.getOrDefault(c,0)+1);
                if(tDict.get(c).equals(winCnt.get(c))){
                    formed++;
                }
            }
            
            while(l<=r && formed==required){
                c = s.charAt(l);
                if(r-l+1 < ans[2]){
                    ans[0] = l;
                    ans[1] = r;
                    ans[2] = r-l+1;
                }
                if(winCnt.containsKey(c)){
                    winCnt.put(c, winCnt.get(c)-1);
                    if(winCnt.get(c) < tDict.get(c)){
                        formed--;
                    }
                }
                l++;
            }
            
            r++;
        }
        return ans[0]==-1?"":s.substring(ans[0], ans[1]+1);
    }
}