76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：

输入：s = "a", t = "a"
输出："a"

提示：

1 <= s.length, t.length <= 105
s 和 t 由英文字母组成

       public String minWindow(String s, String t) {
           if (t.length()>s.length()){
               return "";
           }
           //滑动窗口，窗口性质:[l,r]l和r字符均为满足于t的不同字符,不停滑动右边界，直到找到满足t的位置
           //同时因为可能存在窗口中有重复满足的数据，所以找到r位置后要通过收缩来移动左边界。
           // 例如 bdbbcbacab,abc 第一次满足为bdbbcba,但是存在很多b，所以窗口依旧能够收缩.
           //因为t可能包含重复字符，所以使用HashMap来记录所有字符信息
           Map<Character,Integer> tMap=new HashMap();
           for(int i=0;i<t.length();i++){
               addChar(t.charAt(i),tMap);
           }
           Map<Character,Integer> windowData=new HashMap();
           //用于存放窗口数据
           int l=0;
           int r=0;
           //size用于存放窗口中满足t的字符的数量：注，当一个字符数量超出t中的字符数量时，size不增加。这样维护size，当size等于t的长度时，说明，此时窗口中至少是有一个子字符满足的
           int size=0;
           String ret="";
           while (r<s.length()){
               char preAdd=s.charAt(r);
               //如果拿到的字符存在于t
               if (tMap.containsKey(preAdd)){
                   addChar(preAdd,windowData);
                   //当添加后该字符数量依然小于t中字符数量，那么我们维护下size
                   if (windowData.get(preAdd)<=tMap.get(preAdd)){
                       size++;
                   }
               }
               //当size=t.length时候我们找到了当前的最大满足窗口
               if (size==t.length()){
                   //进行遍历收缩窗口，并保存结果
                   while (l<=r){
                       char item=s.charAt(l);
                       //如果字符不包含，那么直接跳过l
                       if (!tMap.containsKey(item)){
                           l++;
                           continue;
                       }else {
                           //当字符是包含的
                           //先记录下结果
                           if (ret.equals("")){
                               ret=s.substring(l,r+1);
                           }else {
                               ret=ret.length()>(r-l+1)?s.substring(l,r+1):ret;
                           }
                           removeChar(item,windowData);
                           l++;
                           //分两种情况，一种是此时的字符是满足t的非重复字符，当我们移除后，那么window里就为null了
                           //另外一种是重复字符，如果移除后还不小于tMap，那么说明我们窗口还依旧可以收缩。类似于windowdata:bbba   t:bba
                           if (windowData.get(item)==null || windowData.get(item)<tMap.get(item)){
                               size--;
                               break;
                           }
                       }
                   }
               }
               r++;
           }
           return ret;
       }

       private void addChar(char key,Map<Character,Integer> datas){
           if (datas.containsKey(key)){
               datas.put(key,datas.get(key)+1);
           }else {
               datas.put(key,1);
           }
       }
       private void removeChar(char key,Map<Character,Integer> datas){
           if (datas.get(key)==1){
               datas.remove(key);
           }else {
               datas.put(key,datas.get(key)-1);
           }
       }