Minimum Window Substring

基本忘记了，重点做

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".

• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

https://www.youtube.com/watch?v=dzdtzymjM7Awww.youtube.com

[LeetCode] 76. Minimum Window Substring 最小覆盖子串 - Grandyang - 博客园www.cnblogs.com

- 我们最开始先扫描一遍T，把对应的字符及其出现的次数存到数组中。

- 然后开始遍历S，就把遍历到的字母对应的HashMap中的value减一，如果减1后仍大于等于0，total自增1。

- 如果total等于T串长度时，开始循环，纪录一个字串并更新最小字串值。然后将子窗口的左边界向右移，如果某个移除掉的字母是T串中不可缺少的字母，那么total自减1，表示此时T串并没有完全匹配。

class Solution {
    public String minWindow(String s, String t) {
        if(s.length() < t.length()){
            return "";
        }
        
        int[] cnt = new int[128];
        
        for(char c : t.toCharArray()){
            cnt[c]++;
        }
        
        int from = 0;
        int total = 0;
        int min = Integer.MAX_VALUE;
        for(int i = 0, j = 0; i < s.length();i++){
            if(--cnt[s.charAt(i)] >= 0) total++;
            
            //total等于t的长度时说明现在i-j子字符串里包含了所有t中的字母
            while(total == t.length()){
                if(i-j+1 < min){
                    min = i-j+1;
                    from = j;
                }
                
                //窗口向左锁进，当total 小于了t。length时，说明现在的窗口里不包含所有t里的字符，右窗口继续向右扩展
                if(++cnt[s.charAt(j++)] > 0) total--;
            }
        }
        
        return min == Integer.MAX_VALUE? "" : s.substring(from, from+min);
    }
}

class Solution {
    public String minWindow(String s, String t) {
        
        
        
        int[] cnt = new int[128];
        
        for(char c: t.toCharArray()){
            cnt[c]++;
        }
        
        int from = -1,min = Integer.MAX_VALUE ,total = 0;
        
        for(int i = 0, j = 0; i < s.length() && j < s.length(); i++){
            //t里没有的字母都会在这一步变成-1，所以total会在这里统计出来
            //t里出现过的字母，这个时候，i和j之间有所有t里的字母
            if(--cnt[s.charAt(i)] >= 0) total++;
            //判断一下i和j之间的距离，和min比较，并且把j的值给from
            //用来最后判断状态和截取substring
            while(total == t.length()){
                if(i-j+1 < min){
                    min = i-j+1;
                    from = j;
                }
                //这个时候i和j之间t里没出现的字母都是负数，j往右移动，
                //因为t里出现的字母在这一步+1后很有可能大于0， 所以
                //当它大于0时，说明这个时候i和j已经不包括所有t里的字母了，
                //退出当前循环，让i继续右移寻找
                if(++cnt[s.charAt(j++)] > 0) total--;
            }
            
            
        }
        
        return from == -1 ? "" : s.substring(from,from+min);
    }
}