最小覆盖子串

使用一个Map记录每个所需字符的数量，满足要求的判断条件是每个key对应的value都<=0

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param S string字符串
     * @param T string字符串
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // write code here

        // map记录T中所有字符出现的次数
        Map<Character, Integer> map = new HashMap<>();
        for (char c : T.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        String subString = "";
        int minLen = S.length() + 1;
        for (int right = 0, left = 0; right < S.length(); right++) {
            char c = S.charAt(right);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
                while (left <= right && check(map)) {
                    // 此时已经满足要求，更新窗口大小
                    if (minLen > (right - left + 1)) {
                        minLen = right - left + 1;
                        subString = S.substring(left, right + 1);
                    }
                    // 重新向右调整left的位置，打破平衡
                    char a = S.charAt(left);
                    if (map.containsKey(a)) {
                        map.put(a, map.get(a) + 1);
                    }
                    left++;
                }
            }
        }
        System.out.println(subString);
        return subString;
    }

    // 检查窗口内的字符串是否满足要求
    public boolean check(Map<Character, Integer> map) {
        for (Character c : map.keySet()) {
            if (map.get(c) > 0) {
                return false;
            }
        }
        return true;
    }


}

import java.util.*;


public class Solution {
    public String minWindow (String S, String T) {
        // write code here
        if (T.length() > S.length())
            return "";

        int[] cnts = new int[54]; // 大小写英文字母计数
        int[] cntt = new int[54];
        for (Character c : T.toCharArray()) {
            if (Character.isLowerCase(c)) {
                cntt[c - 'a']++;
            } else {
                cntt[c - 'A' + 26]++;
            }
        }

        String res = S + 233; // 未匹配
        int i = 0, j = 0;
        while (j < S.length() || i < j) { // 双指针
            while (j < S.length() && !check(cnts, cntt)) {  // j++
                char c = S.charAt(j);
                if (Character.isLowerCase(c)) {
                    cnts[c - 'a']++;
                } else {
                    cnts[c - 'A' + 26]++;
                }
                j++;
            }
            if (!check(cnts, cntt)) break; // 未匹配break
            if (j - i < res.length()) res = S.substring(i, j);

            char c = S.charAt(i);  // i++
            if (Character.isLowerCase(c)) {
                cnts[c - 'a']--;
            } else {
                cnts[c - 'A' + 26]--;
            }
            i++; 
        }

        return res.length() > S.length() ? "" : res; // 可能没有匹配的
    }

    // s[]中的英文字符是否包含t[]
    private boolean check(int[] s, int[] t) {
        for (int i = 0; i < s.length; i++) {
            if (s[i] < t[i]) return false;
        }
        return true;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param S string字符串
     * @param T string字符串
     * @return string字符串
     */
    // 思路：利用循环压缩左右指针的滑动窗口的方法寻找最小覆盖子串
    public String minWindow (String S, String T) {
        // write code here
        // 存放T的字符出现的次数
        int[] arrT = new int[128];
        for (int i = 0; i < T.length(); i++) {
            arrT[T.charAt(i)]++;
        }
        // left、right分别指向S的滑动窗口的首尾元素，star指向满足要求的最短子串的
        // 起始元素，minLen表示最短子串
        int left = 0, right = 0, star = 0, minLen = Integer.MAX_VALUE, count = T.length();
        // 当右指针在S范围内时，不断循环压缩左右指针，寻找最短子串
        while (right < S.length()) {
            // 右指针指向的元素与arrT中的某个元素相同,说明当前元素能与T中元素匹配,
            // 对count进行--操作,当count==0时说明此时对S的遍历得到的子串能覆盖T
            if (arrT[S.charAt(right)] > 0) count--;
            // 以当期右指针所指向的元素的字符的值作为下标，arrT中该下标对应的元素-1
            // 不论T中是否包含当前字符都要进行-1操作，如果不包含则-1后会对应的元素会
            // 小于0。如果包含但当前遍历S所得到的T中的元素只出现一次，即当前遍历S所
            // 得到的T中元素是不重复的，则-1后arrT对应的元素等于0；如果重复出现则对
            // 应元素小于0,如S="XAXBYCZD",T="XYZ"，当遍历得到的子串为"XAXBY"时满足
            // 要求，但是有两个X，此时进行-1操作会是的arrT[X]=-1<0。大于0小于0将作为
            // 压缩左指针的依据
            arrT[S.charAt(right)]--;
            // count==0时说明此时对S的遍历得到的子串能覆盖T
            if (count == 0) {
                // arrT[S.charAt(left)]<0说明当前子串不需要当前左指针指向的元素也能
                // 覆盖T，因为之前的arrT[S.charAt(right)]--使得T中不包含的字符对应的
                // arrT中的元素小于0。而且子串中重复出现的T中包含元素也在--中使得该字符
                // 对应的arrT的元素小于0，即对出现次数大于1的T包含的元素，可以舍弃靠前
                // 的元素，利用靠后的重复元素进行覆盖T
                while (left < right && arrT[S.charAt(left)] < 0) {
                    // 左指针字符对应的arrT元素+1，如果不+1，那再遍历到重复
                    // 元素时判断会出错
                    arrT[S.charAt(left)]++;
                    // 左指针右移，完成对无用字符的丢弃，即压缩左指针
                    left++;
                }
                // arrT[S.charAt(left)]>=0时退出循环，即当前左指针指向的是T包含的元素
                // 如果当前满足条件的子串长度小于之前记录的子串的长度
                if (right - left + 1 < minLen) {
                    // 将最小子串长度记录为当前子串长度
                    minLen = right - left + 1;
                    // 记录子串起始下标，用于后续对子串的截取返回
                    star = left;
                }
                // 再次向右压缩左指针，即丢弃当前左指针所指的字符，在通过后续的右指针的
                // 右移再次寻找到当前丢弃的元素,再次完成对T覆盖,然后再不断的循环压缩左右
                // 指针
                // 左指针向右压缩前先对arrT中的元素进行+1，用于下轮外层循环
                arrT[S.charAt(left)]++;
                // 计数+1，用于外层循环
                count++;
                // 再次向右压缩左指针
                left++;
            }
            // 右指针右移，重新寻找上一步丢弃的字符，以构成覆盖子串
            right++;
        }
        return minLen == Integer.MAX_VALUE ? "" : S.substring(star, star + minLen);
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // 存放目标字符串的字符数量
        int[] need = new int[128];
        for (int i = 0; i < T.length(); i++) need[T.charAt(i)]++;
        // 目标字符串中的字符个数
        int count = T.length();
        // 左右指针,用于维护滑动窗口
        int left = 0, right = 0;
        // 记录窗口的起点与长度,用于截取字符串;长度初始化为一个不可能的最大值
        int start = 0, len = S.length() + 1;

        while (right < S.length()) {
            // 滑动窗口右侧
            char c = S.charAt(right++);
            // 仅当前字符的需要数量大于0时,需要的目标字符数量减一
            if (need[c] > 0) {
                count--;
            }
            // 所有字符都进行自减操作,不需要的字符会被减到负数,需要的字符先减到0,再减到负数
            need[c]--;

            // 当count为0时,说明当前窗口中的字符可以覆盖目标字符串T
            if (count == 0) {
                // 当need中,窗口左侧的字符为负数时,说明该字符是多余的(不论是否是T中包含的字符),滑动窗口左侧,直至最左侧的字符非多余,此时窗口为右侧固定情况下的最小覆盖子串
                while (need[S.charAt(left)] < 0) {
                    need[S.charAt(left++)]++;
                }
                // 判断长度,并记录起点和长度
                if (right - left < len) {
                    len = right - left;
                    start = left;
                }
                // 将窗口左侧字符滑出,need中该字符需要的数量自增(为1)
                need[S.charAt(left++)]++;
                // 需要的目标字符数量也自增(为1)
                count++;
            }
        }
        // 若长度仍为不可能的最大值,说明没有覆盖子串,否则通过start和len进行截取
        return len == S.length() + 1 ? "" : S.substring(start, start + len);
    }
}

public boolean check(int[] hash){//检查hash数组中是否有小于0的  如果没有小于0的，那就可以缩短左窗口
        for(int i=0;i<hash.length;i++){
            if(hash[i]<0) return false;//因为hash本身就已经被初始化为负数了
        }
        return true;
    }
    public String minWindow (String S, String T) {
        // 从S中找T
        //遍历字符串T，加入哈希表，出现次数计为负数
        //遍历字符串S，如果匹配上了，把哈希表中对应字符+1
        //遍历过程中维护一个窗口，如果哈希表中所有元素>0，则找全了，左窗口收缩，找最小的窗口；否则，右移窗口继续匹配。
        //如果匹配到最后，窗口left（初始化为-1）始终没有右移，说明没有找到，返回空串
        //返回结果集，截取刚刚记录的窗口就是ans
        int cnt=S.length()+1;
        int[] hash=new int[128];//开了个数组而已，实际上不会用完这128个空间
        for(int i=0;i<T.length();i++){
            hash[T.charAt(i)]=hash[T.charAt(i)]-1;//哈希表初始化为负数，找的时候再加为正   在T中出现几次，在hash[]中就负几
        }
        //双指针
        int slow=0;
        int fast=0;
        //记录左右区间  left\right用来截取字符串
        int left=-1;
        int right=-1;
        for(fast=0;fast<S.length();fast++){
               char c=S.charAt(fast);
               hash[c]++;//目标字符匹配，则+1   如果hash[]中有这个字符，那就在hash中++这个字符出现的次数

               while(check(hash)){//没有小于0的说明都覆盖了，开始缩小左窗口
                    if(cnt>fast-slow+1){//比较窗口长度
                        cnt=fast-slow+1;//更新窗口
                        left=slow;
                        right=fast;
                    }
                    c=S.charAt(slow);//记录左窗口的值
                    hash[c]--;//缩小窗口时-1
                    slow++;//窗口缩小
               }        
        }
        if(left==-1) return "";//找不到的情况
        return S.substring(left,right+1);//左开右闭

    }

import java.util.*;


public class Solution {
    public boolean Judge(HashMap<Character, Integer> hs) {
        Collection<Integer> col = hs.values();
        for (int i : col) {
            if (i < 0) return false;
        }
        return true;
    }
    public String minWindow (String S, String T) {
        if (T.length() > S.length()) return"";
        if (T.length() == S.length() && !S.equals(T)) return "";
        if (S.equals(T)) return S;
        HashMap<Character, Integer> hs = new HashMap<>();
        for (int i = 0; i < T.length(); i++) {
            char c = T.charAt(i);
            if (!hs.containsKey(c)) hs.put(c, -1);
            else hs.put(c, hs.get(c) - 1);
        }//初始化完成哈希表
        int left = 0;
        int min_left = 0;
        int min_length = S.length() + 1;
        for (int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);
            if (hs.containsKey(c))
                hs.put(c, hs.get(c) + 1);
            if (Judge(hs)) {
                if (i - left + 1 < min_length) {
                    min_left = left;
                    min_length = i - left + 1;
                }
                char c1 = S.charAt(left);
                if (hs.containsKey(c1))
                    hs.put(c1, hs.get(c1) - 1);
                left++;
                while (Judge(hs)) {
                    char c2 = S.charAt(left);
                    if (hs.containsKey(c2))
                        hs.put(c2, hs.get(c2) - 1);
                    left++;
                }
                if (i - left + 2 < min_length) {
                    min_left = left-1;
                    min_length = i - left + 2;
                }

            }
        }
        if(min_length==S.length()+1) return "";
        return S.substring(min_left, min_left + min_length);
    }
}

import java.util.*;


public class Solution {
    public String minWindow (String S, String T) {
        // write code here
        int[] hs = new int[128];//map
        int[] ht = new int[128];
        for (int i = 0; i < T.length(); i++) {
            ht[T.charAt(i)]++;
        }
        String res = null;
        // i 是快 j是慢指针
        for (int i = 0, j = 0, cnt = 0; i < S.length(); i++) {
            //添加当前字符串
            hs[S.charAt(i)]++;
            if (hs[S.charAt(i)] <= ht[S.charAt(i)]) cnt++; //更新有效字符串数量
            //去除冗余字符,j 向前移动
            while (hs[S.charAt(j)] > ht[S.charAt(j)] && cnt == T.length()) hs[S.charAt(j++)]--;
            //完全覆盖
            if (cnt == T.length()) {
                // 为空或者大于窗口数量
                if (res == null || res.length() > i - j + 1) {
                    res = S.substring(j, i + 1);
                }
            }
        }
        return res == null ? "" : res;
    }
}

本方法写的有点丑陋，但是所有题解都是大同小异。双指针一个left 一个 right，中间夹着的就是子串，
right不停往右走，一旦之间的子串符合要求，left收缩直到长度最小，
当子串不符合要求的时候，right 继续往右走。


import java.util.*;


public class Solution {
    /**
     *
     * @param S string字符串
     * @param T string字符串
     * @return string字符串
     */
    public boolean contains(HashMap<Character,Integer> map1, HashMap<Character,Integer> map2){
        Set<Character> kset1 = map1.keySet();
        Set<Character> kset2 = map2.keySet();
        for(char c : kset2){
            if(!kset1.contains(c) || map1.get(c)<map2.get(c)) return false;
        }
        return true;
    }
    public String minWindow (String S, String T) {
        // write code here
        HashMap<Character,Integer> mapS = new HashMap<>();
        HashMap<Character,Integer> mapWindow= new HashMap<>();
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < T.length(); i++) {
            set.add(T.charAt(i));
            if(mapS.containsKey(T.charAt(i))) mapS.put(T.charAt(i), mapS.get(T.charAt(i))+1);
            else mapS.put(T.charAt(i), 1);
        }
        int len = 999, left = 0;
        String res = "";
        for (int i = 0; i < S.length(); i++) {
            if (set.contains(S.charAt(i))){
                if(mapWindow.containsKey(S.charAt(i))) mapWindow.put(S.charAt(i), mapWindow.get(S.charAt(i))+1);
                else mapWindow.put(S.charAt(i), 1);
            }
            while(contains(mapWindow,mapS)){
                if(i-left+1<len){
                    len = i-left+1;
                    res = S.substring(left,i+1);
                }
                if(set.contains(S.charAt(left))) mapWindow.put(S.charAt(left), mapWindow.get(S.charAt(left))-1);
                left++;

            }
        }
        return res;
    }
}

import java.util.*;


public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // write code here
        //特殊情况---s不包含t的所有字符
        for(int i=0;i<=T.length()-1;i++){
            if(!S.contains(String.valueOf(T.charAt(i)))){
                return "";
            }
        }
        //一般情况
        //ht
        Map<Character,Integer> ht=new HashMap<Character,Integer>();
        for(int i=0;i<=T.length()-1;i++){
            ht.put(T.charAt(i),ht.getOrDefault(T.charAt(i),0)+1);
        }
        //hs
        int count=0;
        String res="";
        Map<Character,Integer> hs=new HashMap<Character,Integer>();
        int min_len=Integer.MAX_VALUE;
        for(int left=0,right=0;right<=S.length()-1;right++){
            char c=S.charAt(right);
            hs.put(c,hs.getOrDefault(c,0)+1);
            if(ht.containsKey(c)&&hs.get(c)<=ht.get(c)){
                count++;
            }
            while(left<right&&(!ht.containsKey(S.charAt(left))||hs.get(S.charAt(left))>ht.get(S.charAt(left)))){
                hs.put(S.charAt(left),hs.get(S.charAt(left))-1);
                left++;
            }
            if(count==T.length()&&right-left+1<min_len){
                min_len=right-left+1;
                res=cut_string(S,left,right);
            }
        }
        return res;

        
    }
    public String cut_string(String s,int i,int j){
        String res="";
        for(int index=i;index<=j;index++){
            res=res+String.valueOf(s.charAt(index));
        }
        return res;
    }
}

import java.util.*;
public class Solution {
    public String minWindow (String S, String T) {
        int res = Integer.MAX_VALUE, index = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < T.length(); i++) {
            char c = T.charAt(i);
            if(!map.containsKey(c)) map.put(c, 1);
            else map.put(c, map.get(c) + 1);
        }

        int left = 0, right = 0;
        while(right < S.length()){
            char c = S.charAt(right++);
            if(!map.containsKey(c)) continue;
            map.put(c, map.get(c)-1);

            while(isValid(map)){
                if(res > right - left){
                    res = right - left;
                    index = left;
                }
                char tmp = S.charAt(left++);
                if(map.containsKey(tmp)) map.put(tmp, map.get(tmp)+1);
            }
        }
        return res == Integer.MAX_VALUE ? "" : S.substring(index, index+res);
    }

    public boolean isValid(HashMap<Character, Integer> map){
        for (Integer value : map.values()) {
            if(value>0) return false;
        }
        return true;
    }
}

import java.util.*;


public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // write code here
        if(S == null || S == "" || T == null || T == "" || S.length() < T.length()){
            return "";
        }
        int[] need = new int[128];
        int[] have = new int[128];
        int lens = S.length();
        int lent = T.length();
        int count = 0;
        for(int i = 0; i < lent; i++){
            need[T.charAt(i)]++;
        }
        int left = 0;
        int right = 0;
        int startIndex = 0;
        int min = lens+1;
        while(right < lens){
            char r = S.charAt(right);
            if(need[r] == 0){
                right++;
                continue;
            }
            if(have[r] < need[r]){
                count++;
            }
            right++;
            have[r]++;
            while(count == lent){
                if(right - left < min){
                    min = right - left;
                    startIndex = left;
                }
                char l = S.charAt(left);
                if(need[l] == 0){
                    left++;
                    continue;
                }
                 if(have[l] == need[l]){
                    count--;
                }
                left++;
                have[l]--;
            }
        }
        if(min == lens+1){
            return "";
        }
        return S.substring(startIndex,startIndex+min);
    }
}

import java.util.*;


public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // hash表
        int[] hash = new int[128];
        
        for(int i = 0; i < T.length(); i++) {
            hash[T.charAt(i)]--;
        }
        
        // 快慢双指针 即窗口的边界
        int slow = 0, fast = 0;
        // 记录最短的字符串长度
        int min = Integer.MAX_VALUE;
        // 最短的字符串长度左右边界
        int left = -1, right = -1;
        
        while(fast < S.length()) {
            
            // 当窗口没有覆盖T中全部字符
            while(fast < S.length() && !check(hash)) {
                char c = S.charAt(fast);
                hash[c]++;
                fast++;
            }
            // 当窗口覆盖了T中全部字符
            while(slow < S.length() && check(hash)) {
                char c = S.charAt(slow);
                hash[c]--;
                slow++;
            }
            if(min > fast - slow + 1) {
                min = fast - slow + 1;
                left = slow - 1;
                right = fast;
            }
        }
        // 当slow指针没有动过，说明S没有覆盖过T中全部字符，返回""
        if(left == -1) return "";
        return S.substring(left, right);
    }
    
    private boolean check(int[] hash) {
        for(int i = 0; i < hash.length; i++) {
            if(hash[i] < 0) return false;
        }
        return true;
    }
}