最小覆盖子串

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;
    }
}

• 核心：什么条件下，才更新窗口中的数据。
• 思考1：当移动右指针right扩大窗口时，到达当前字符，需要做什么事，更新哪些数据，求可行解？
• 思考2：什么条件下，窗口应该暂停扩大，开始移动left来缩小窗口,求最优解？
• 思考3：当移动左指针left缩小窗口时，到达当前字符，需要做什么事，更新哪些数据，求最优解？
• 思考4：需要的最优解应该在扩大窗口时更新，还是在缩小窗口时更新?
  如果一个字符进入窗口，应该增加 window 计数器；如果一个字符将移出窗口的时候，应该减少 window 计数器；当 valid 满足 need 时应该收缩窗口；应该在收缩窗口的时候更新最终结果。

import java.util.*;


public class Solution {
    /**
     *
     * @param S string字符串
     * @param T string字符串
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // write code here
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();
        for (int i = 0; i < T.length(); ++i) {
            char ch = T.charAt(i);
            need.put(ch, need.getOrDefault(ch, 0) + 1);
        }
        int left = 0, right = 0; // 左闭右开的窗口
        int valid = 0;
        // 记录最小覆盖子串的开始索引和长度
        int start = 0, len = Integer.MAX_VALUE;
        while (right < S.length()) {
            char c = S.charAt(right);
            // 当右指针到达某个字符时要做的事
            if (need.containsKey(c)) { // 目标字符串包含该字符串时，才更新窗口
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) { // 窗口中的当前字符c已经满足需求
                    valid++;
                }
            }
            ++right; // 扩大窗口

            while (valid == need.size()) { // 找到第一个满足need的位置，窗口停止扩大
                // 计算窗口起点和长度
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // 左指针到达某个字符时需要做的事
                char d = S.charAt(left);
                if (window.containsKey(
                            d)) { // 窗口中包含当前字符d，需要更新窗口
                    if (window.get(d).equals(need.get(d))) { // 数目匹配
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
                ++left;  // 缩小窗口
            }
        }

        //System.out.println("left: " + left + ", right: " + right);
        StringBuilder res = new StringBuilder();
        if (len != Integer.MAX_VALUE) {
            for (int i = start; i < start + len; i++) {
                res.append(S.charAt(i));
            }
        }
        return new String(res);
        // return len == Integer.MAX_VALUE ? "" : S.substring(start, start + len);
    }
}

public String minWindow (String S, String T) {
        // write code here
       if (S==null||T==null||S.length()==0||T.length()==0||S.length()<T.length())
            return "";
        
        //代表当前滑动窗口中各个字符的数量
        int[] need=new int[128];
        //代表字符串T中各字符的数量
        int[] own=new int[128];
        for (int i=0;i<T.length();i++)
            need[T.charAt(i)]++;
        //代表滑动窗口中字符串与T中字符串的差距，当count==T.length的时候，代表滑动
        //窗口中拥有T中所有字符
        int count=0;
        int l=0;
        int r=0;
        //记录最小覆盖子串的开始位置
        int start=0;
        //记录最小覆盖子串的长度
        int minLen=Integer.MAX_VALUE;
        while (r<S.length()){
            char c = S.charAt(r);
            //证明t中并没有这个字符，这个字符没用，直接r++，continue
            if (need[c]==0){
                r++;
                continue;
            }
            //证明滑动窗口中还缺这个字符，有了之后，差距缩小了，所以count++
            if (own[c]<need[c])
                count++;
            own[c]++;
            r++;
            //代表窗口中拥有所有的t中的字符了
            while (count==T.length()){
                //判断长度，因为之前r++了，所以这里不是r-l+1
                if (r-l<minLen){
                    minLen=r-l;
                    start=l;
                }
                
                //开始移动左指针
                char tmp= S.charAt(l);
                //代表t中没有这个字符，不要了也没事，所以直接l++，continue
                if (need[tmp]==0){
                    l++;
                    continue;
                }
                //如果此时need【tmp】<own【tmp】
                //证明窗口中有多余的字符，所以尽管这个字符是t中需要的，但删除了也没问题
                //因为剩下的还够
                //只有need【tmp】等于own【tmp】的时候，表明
                //如果这个时候，这个字符没了，窗口中就相比t，差一个字符了，所以count--
                if (need[tmp]==own[tmp])
                    count--;
                
                own[tmp]--;
                l++;
            }
        }
        
        //代表没有覆盖子串
        if (minLen==Integer.MAX_VALUE)
            return "";
        return S.substring(start,start+minLen);

import java.util.*;


public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // write code here
        //暴力法
        int start=0;
        int end=0;
        ArrayList<Character> arr = new ArrayList<>();
        for(int i=0;i<T.length();i++){
            arr.add(T.charAt(i));
        }
        ArrayList<Character> chars=new ArrayList<>(arr);
        int minLen=Integer.MAX_VALUE;
        int j=0;
        int i=0;
        while(j<S.length()){
            while(j<S.length() && !arr.contains(S.charAt(j))) j++;
//             start=j;
            for(i=j;i<S.length();i++){
                if(!arr.isEmpty() && arr.contains(S.charAt(i))){
                    arr.remove((Character)S.charAt(i));
                }else if(arr.isEmpty()){
//                     end=i;
                    break;
                }
            }
            if(arr.isEmpty() && i-j<minLen){
                start=j;
                end=i;
                minLen=i-j;
            }
            j++;
            arr=new ArrayList<>(chars);
        }
        
        return minLen<=0?"":S.substring(start,end);