76 Minimum Window Substring.java

/*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).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".*/

//方法1：使用2个Hash
//targetHash来表示目标值字典；sourceHash表示当前window中的字符统计
//（1）九章做法——使用isValid()函数，循环i（左指针）
    public String minWindow(String s, String t) {
        if(s == null || t == null ||t.length() == 0 || s.length() < t.length()){
            return "";
        }
        int[] sHash = new int[256];
        int[] tHash = new int[256];
        for(char c: t.toCharArray()){
            tHash[c]++;
        }
        int i = 0, j = 0;
        int minLen = Integer.MAX_VALUE;
        String str = "";
        while(i < s.length()){ //循环左下标
            
            while(!isValid(tHash, sHash) && j < s.length()){//(1)没到结尾时，还没找到：
                char cj = s.charAt(j);
                sHash[cj]++;//增加j对应的hash值，j++
                j++;
            }
            if(isValid(tHash, sHash)){//(2)找到了，更新min相关值
                if(j - i < minLen){
                    minLen = Math.min(minLen, j - i);
                    str = s.substring(i, j); //注意是 substring 全小写
                }
            }
            //(3)不管是找到了，还是仅仅没找到但是j到终点了，都需要更新i了
            char ci = s.charAt(i);
            sHash[ci]--;//减掉i对应的hash值；i++
            i++;
        }
        return str;
    }
    public boolean isValid(int[] tHash, int[] sHash){
        for(int i = 0; i < 256; i++){
            if(tHash[i] > sHash[i]){
                return false;
            }
        }
        return true;
    }
//(2) 肖做法- 循环j（右指针），好理解，细节多
public String minWindow(String s, String t) {
        if(s == null || t == null ||t.length() == 0 || s.length() < t.length()){
            return "";
        }
        //用int[] hash来当做mapping，比hashmap省空间，也好操作
        //char字符本身即可作为下标：用hash[A]的值来表示A出现的频次
        int[] sHash = new int[256]; //当前window中的字符统计
        int[] tHash = new int[256]; //目标值字典
        for(char c: t.toCharArray()){//构建字典
            tHash[c]++; //目标字符对应值为1，其他的都为0
        }
        int minLen = Integer.MAX_VALUE;
        String str = "";
        int count = 0; //统计已经在window中的有效字符个数
        int i = 0;
        for(int j = 0;j < s.length();){ //循环右指针
            char cj = s.charAt(j++); //j更新在这里
            if(tHash[cj] != 0){ //如果当前字符是在字典中的 （后面有类似的这四行：在字典中的字符，才更新sHash+（如果不超过字典频率）调整count）
                sHash[cj]++;
                if(sHash[cj] <= tHash[cj]){ //还没收集到字典中全部要求
                    count++;
                }
                while(count == t.length()){ //while收集到字典中全部要求
                    if(j - i  < minLen){ //得到更小窗口，更新minLen和str
                        minLen = j - i; //j已经+1了，所以距离就是j - i
                        str = s.substring(i, j);
                    }
                    char ci = s.charAt(i++);// i更新在这里
                    if(tHash[ci] != 0){ //是字典中的字符，就更新下sHash
                        sHash[ci]--;
                        if(sHash[ci] < tHash[ci]){
                            count--;
                        }
                    }
                }
            }
        }
        return str;
  }
//方法二：1个hash 
public class Solution {    
    public String minWindow(String s, String t) {
        int[] cnt = new int[256];
        for (char c : t.toCharArray()) cnt[c]++;
        
        int min = Integer.MAX_VALUE, from = 0, total = t.length(); //总需求书
        for (int i = 0, j = 0; i < s.length(); i++) { //循环i（右指针）
            if (cnt[s.charAt(i)]-- > 0) total--; //（1）操作右指针数：扫过的数（右指针）如果是目标字符，值减1，总数也减1
            while (total == 0) {  // total=0 means valid window （2）while找到有效窗口
                if (i - j + 1 < min) {//try to update the min length （2.1）更新min值
                    min = i - j + 1;
                    from = j;
                }
                if (++cnt[s.charAt(j++)] > 0) total++; //（2.2）操作左指针：左指针如果是目标字符，（从当前window剔除，i++寻找下一个），值加1，总数也加1
            }
        }
        return (min == Integer.MAX_VALUE) ? "" : s.substring(from, from + min); //返回值需判断
    }
}

//follow-up:如果参数为HashSet来表示目标字典（相当于只有字符，没有频次统计）
public class Solution {
    public String minWindow(String s, HashSet<Character> thash) {
        String res = "";
        int[] shash = new int[256];//shash records num of all chars appeared in dict that are in curr window
        int count = 0;//num of |effective| chars in curr window,while it equals t.length(), we will try to shink the window
        int min = s.length() + 1;
        for (int left = 0, right = 0; right < s.length();) {
            char r = s.charAt(right++);
            if (thash.contains(r)) {//if it's in the dict
                shash[r]++;//num of |valid| chars in curr window increases
                if (shash[r] == 1) {//if the num of valid char is <= what target needed
                    count++;
                }
                while (count == thash.size()) {
                    if (right - left < min) {//first try to update the min length and res
                        min = right - left;
                        res = s.substring(left, right);
                    }
                    char l = s.charAt(left++);
                    if (thash.contains(l)) {//if it's in the dict
                        shash[l]--;//num of |valid| chars in curr window decreses
                        if (shash[l] == 0) {//if the num of valid char is < what target needed
                            count--;
                        }
                    }
                }
            }
        }
        return res;
    }
}