* 76. Minimum Window Substring - hard

解题思路：

1. 利用Array的index存两个string的词频。
2. 什么情况下找到一个valid的字符；
3. 什么情况下找到一个valid的完整字符串；

当找到这个字符串的时候：

1. 跳过前面多余的字符；
2. 更新需求，即最短长度；若更新了，记录开头和结尾；
3. 跳过这个字符串的首字符，继续扫(found也要减一)。

====
看到题的第一反应，先数S中每个字母有多少个，以后后面一定要一个一个减掉。
我最初的想法：
s = “DADOBECODEBANC”
t = “ABC“
okay, scan S, start from the letter that also appears in T. here, we start from ADOBEC. this is an possible answer。
Then we skip the first A (cnt A--), start from B, BECODEBA. But when we arrives B, which locates between E and A, we skip the first B (cnt B --), since it will definitely gives shorter answer. keep working till the end.
因为先要存t的字频，之后查表，所以一定会用到hashTable/hashMap;

看了答案，答案用了hash的思想，但是只用array就存储了cnt的信息。

public class Solution {
    public String minWindow(String s, String t) {
        int[] sCnt = new int[255];
        int[] tCnt = new int[255];
        
        for (int i=0; i<t.length(); i++) {
            tCnt[t.charAt(i)]++;
        }
        
        int start = 0;
        int begin = -1, end = s.length();
        int found = 0, minLen = s.length();
        
        for (int i=0; i<s.length(); i++) {
            char c1 = s.charAt(i);
            sCnt[c1]++;
            if(sCnt[c1] <= tCnt[c1])    found++;
            if(found == t.length()) {
                while (start<i && sCnt[s.charAt(start)]>tCnt[s.charAt(start)]) {
                    sCnt[s.charAt(start)]--;
                    start++;
                }
                
                if(i-start < minLen) {
                    minLen = i-start;
                    begin = start;
                    end = i;
                }
                
                sCnt[s.charAt(start)]--;
                start++;
                found--;
            }
        }
        return begin == -1 ? "" : s.substring(begin, end+1);
    }
}

总结一下：直接在代码里写吧。

public class Solution {
    public String minWindow(String s, String t) {
        int[] sCnt = new int[255];
        int[] tCnt = new int[255];
        
        for (int i=0; i<t.length(); i++) {
            tCnt[t.charAt(i)]++;
        }
        
        int start = 0;
        int begin = -1, end = s.length();
        int found = 0, minLen = s.length();
        
        for (int i=0; i<s.length(); i++) {
            char c1 = s.charAt(i);
            sCnt[c1]++;
            /** 如果算上这个字符后，数量不超过t中这个字符的数量，那么这个字符算是valid(即找到一个匹配的字符)；
             */
            if(sCnt[c1] <= tCnt[c1])    found++;
            /** 找到一个valid的字符串。
             */
            if(found == t.length()) {
                /** 这个字符串end一定是i。现在需要找到这个字符串的起始位置。
                 * 起始位置那个字符在s中出现的次数一定和在t中出现的次数一样多；
                 * 所有那些s中出现次数比t中多的，一定是多余的，从前往后扫，然后全部删掉。
                 * 记得每次从s中散掉的时候，s对这个字符的cnt也要减一。
                 */ 
                while (start<i && sCnt[s.charAt(start)]>tCnt[s.charAt(start)]) {
                    sCnt[s.charAt(start)]--;
                    start++;
                }
                /** 更新minLen，如果更新了，那么记录下这个长度的起始点和终点。 
                 */
                if(i-start < minLen) {
                    minLen = i-start;
                    begin = start;
                    end = i;
                }
                
                /** 把开头的start跳过，注意sCnt也要减一，继续扫。
                 */ 
                sCnt[s.charAt(start)]--;
                start++;
                found--;
            }
        }
        return begin == -1 ? "" : s.substring(begin, end+1);
    }
}