摘要：使用而不是因為我們需要的是最值，中間值我們不在乎，所以一次收斂到最小。下面來三個需要查重并且記錄上次出現的位置，選擇以為例，走到用做檢查，發現出現過，把移到的下一個。是上個題目的簡易版，或者特殊版。

這里聊一聊解一類問題，就是滿足某一條件的substring最值問題。
最開始我們以Minimum Window Substring為例，并整理總結leetcode里所有類似題目的通解。

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

我們要把問題拆解成三個字問題：唯一的表示substring, 檢查substring是否符合要求，記錄最值。
1.
如何唯一的表示一個substring, 有兩種方法，一種用頭尾指針，一種用尾指針加substring長度。
2.
檢查substring是否符合要求，這道題目要求包含T中的每個字母，所以我們需要一個counter來記錄T里每個character出現的次數，空間O(26) O(128) O(256) 都行， 可以和面試官討論。類似題目唯一變化的就是這個部分，可以是每個字符只能出現一次，最多出現兩個不同字符，每個字符最多出現K次等等。
3.
記錄最值。根據掃描方法的不同，長度有時為r-l,此時r不包含在substring里，有時為r-l+1,此時包含在substring里。

這篇博客主要講第二個子問題，如何判斷substring是否符合要求。以Minimum Window Substring為例。

public class Solution {
    public String minWindow(String s, String t) {
        // empty check
        if(s == null || t == null || s.length() == 0 || t.length() == 0) return "";
        // initial counter for valid check
        int[] counter = new int[128];
        for(char c : t.toCharArray()){
            counter[c]++;
        }
        // variables help represent substring and min/max
        char[] chs = s.toCharArray();
        // 變量名解釋，i表示頭即先開始掃描的指針，j表示尾。i,j對counter的操作相反，一個加一個減或者一個減一個加。 
        // 上面的counter記錄每個字符出現次數，count表示substring里滿足條件的字符出現總次數（可以從0加到count,也可以從count減少到0.
        int j = 0, i=0, minLen = Integer.MAX_VALUE, start = 0, count = t.length();
        
        //這里可以使用for和while兩種循環，個人偏向for, 因為i指針要一次走一個字符遍歷完整個string.
        for( ; i < chs.length; i++){      //逐個掃描
            // 我們包含了第i個元素，并且要立即判斷是否滿足條件。使用--x, 而不是x--.
            if(--counter[chs[i]] > -1) {
                count--;
            }
            // 因為我們需要的是最值，中間值我們不在乎，所以一次收斂到最小。
            while(count == 0) {     // 快速收緊
                if(i -j + 1< minLen) {
                    minLen = i - j + 1;
                    start = j;
                }
                // 用 == 0 判斷是因為有的substring里個別字符可能偏多，多余的字符不會算作滿足條件。下方有簡單的例子。 
                // 一次只移動一個char, 所以這里用 == 0
                if(counter[chs[j++]]++ == 0) {
                    count++;
                }
            }
        }
        
        return minLen == Integer.MAX_VALUE ? "" : new String(chs, start, minLen);
    }
}

X表示占位符，不是字母X。（使用空格會被自動消除，所以這里用了X）
S: ADOBECODEBANC T: ABC
i: ADOBECXXXXXXXX
j: XDOBECXXXXXXX
i: XDOBECODEBAXX
j: XXXXXXODEBAXX
注意這一步j最后落在了C后面，而不是B的后面。因為B在T里只出現了一次, i在掃描的時候會減小兩次，counter[B] = -1, counter[c] = 0
i: XXXXXXODEBANC
j: XXXXXXXXXBANC

將S，T里字符換成String,變成Leetcode 30, Substring with Concatenation of All Words. 
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters. 
s: "barfoothefoobarman",  words: ["foo", "bar"], You should return the indices: [0,9]

字符長度為K，我們可能從0， 1， 2， K-1開始組成不同字符， 從K開始會和從O開始重合了。代碼如下，不過多解釋，可以直接跳過。

public class Solution {
    public List findSubstring(String s, String[] words) {
        List res = new ArrayList();
        int N = s.length(), M = words.length, K = words[0].length();
        // check input
        if(s == null || K == 0 || N < M*K) return res;
        Map map = new HashMap<>(), curMap = new HashMap<>();
        // initial counter
        for(String word: words) {
            map.put(word, map.getOrDefault(word,0) + 1);
        }
        // str denote first word, temp denote last word
        String str = null, temp = null;
        for(int i=0; i< K; i++) { 
            int count = 0;
            // two poniter scan, each time move K steps
            for(int l=i, r=i; r+K <= N; r += K) {
                str = s.substring(r, r+K);
                if(map.containsKey(str)) {
                    curMap.put(str, curMap.getOrDefault(str,0) + 1);
                    
                    if(curMap.get(str) <= map.get(str)) count++;
                    // has a word above the counter of it
                    while(curMap.get(str) > map.get(str)) {
                        temp = s.substring(l, l+K);
                        curMap.put(temp, curMap.get(temp) - 1);
                        l += K;
                        if(curMap.get(temp) < map.get(temp)) count--;
                    }
                    // should be exactly M, when meet, delete last word
                    if(count == M){
                        res.add(l);
                        temp = s.substring(l, l+K);
                        curMap.put(temp, curMap.get(temp) - 1);
                        l += K;
                        count--;
                    }
                } else {
                    curMap.clear();
                    count = 0;
                    l = r + K;
                }
            }
            curMap.clear();
        }

        return res;
    }
}

下面來三個longest substring.
LC3 Longest Substring Without Repeating Characters
需要查重并且記錄上次出現的位置，選擇map.
以abcdba為例，i走到b, 用map做檢查，發現出現過，把j移到map.get(b)的下一個。
i走到a, 用map做檢查，發現出現過，把j移到map.get(a)的下一個。發現不對，因為下一個字符是b已經出現過兩次，所以需要一個比較，取map.get(b),map.get(a)的最大值。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        // empty check
        if(s == null || s.length() == 0) return 0;
        // 
        Map map = new HashMap<>();
        // scan whole string and calculte
        int len = 0;
        char[] chs = s.toCharArray();
        for(int i=0, j=0; i len) {
                len = i-j+1;
            }
        }
        return len;
    }
}

LC340. Longest Substring with At Most K Distinct Characters

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example, Given s = “eceba”,
T is "ece" which its length is 3.

counter記錄每個字符出現次數。 count表示有多少個不同字符，題目要求最多出現k個。

public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        // corner case
        if(s== null || s.length() == 0)  return 0;
        // counter, count denote k
        int[] counter = new int[128];
        // l denote tail, r denote head, two pointer scan
        int j = 0, len = 0, count = 0;
        for(int i=0; i k) { 
                while( --counter[s.charAt(j++)] > 0);   
                count--;
            }
            if(i - j + 1 > len) {
                len = i - j +1;
            }
        }
        // return max
        return len;
    }
}

LC159. Longest Substring with At Most Two Distinct Characters

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example, Given s = “eceba”,
T is "ece" which its length is 3.

是上個題目的簡易版，或者特殊版。只有兩個字符，我們就不需要一個數組了，只需要兩個位置標記就行。p1, p2. 為了讓計算最值方便，讓p1始終小于p2.

這里需要注意的就是p1,p2在repeating characters出現的時候，同時會指向這個字符串的最后一個。
在判斷第三個字符是否出現的時候，首先要比較p1 != p2.

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if(s.isEmpty()) return 0;
        int p1 = 0, p2 = 0, max = 1, len = 1; 
        char[] chs = s.toCharArray();
        for(int i=1; i max) max = len;
                len = i - p1;       // always keep p1,p2 ordered p1<=p2
                p1 = p2;
                p2 = i;
            } else {  
                if(chs[i] == chs[p1]) {  // 0 or repeating charcters lead to p1=p2
                    p1 = p1 == p2 ? i:p2;
                }
                len++;
                p2 = i;
            }
        }
        
        if (len > max) max = len;
        return max;
    }
}

今天先寫到這里，以后補充。