Minimum Window Substring !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Q:
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".
Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

A:
之前根据max-crossing subArray的想法，貌似在计算的cross时候，还是不够efficiency.
是不是，可以根据KMP算法呢？？？


双指针，动态维护一个区间。尾指针不断往后扫，当扫到有一个窗口包含了所有T的字符后，然后再收缩头指针，直到不能再收缩为止。最后记录所有可能的情况中窗口最小的
------------复杂度呢？？？？ 由于被查找的string最多也就265个字符。因此，可以把其看做是constant的， 那么，复杂度就是O(n)了 -------------------


这道题目，最大的注意之处，就是head 和tail指针的 update 方式。不能处理得太粗糙。



Mistakes:
1: 在find cross 的时候，由于low high是inclusive的，因此在计算长度的时候， 要high-low +1
            for (int i = leftStart; i <= rightEnd+1 - curLen; i++) {
2: 题意理解错误。

Input:	"a", "aa"
Output:	"a"
Expected:	""

从这里来看， 允许重复的字母的。 也必须出现最少相同的次数。

3: 认为最后tail会== S.length() 是正确的， 但是，之间，还依然是inclusive的。  所以，不需要把它当做 exclusive来对待。

4： 哎，犯了一个很SB的错误。 在update  tail 指针的时候，要对每个位置，检查加上后，是否满足match条件，如果是，则退出来。
但是，原本，就随手写了个while (!allFind(count, times) && tail < S.length()) {   这样，逻辑是比较混乱的。


Learned:


-------------第二遍-----------， T中是有计数的，例如S= "a", T = "aa" ,结果应该是false------
 另外，这次，当S超过10000的时候，会有说String index out of 10000的错误。不知道为什么？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
？？？？？？？？？？？？？？？？

public class Solution {
    public String minWindow(String S, String T) {
        if(S==null || T == null)
            return "";
        HashMap<Character, Integer> origMap = new HashMap<Character, Integer>();
        HashMap<Character, Integer> findMap = new HashMap<Character, Integer>();
        HashMap<Character, Integer> totalMap = new HashMap<Character, Integer>();
        int start = 0,  minStart = S.length(),minEnd = Integer.MAX_VALUE;
        for(int i = 0;i<T.length();i++ ){
            char ch = T.charAt(i);
            if(origMap.containsKey(ch)){
                origMap.put(ch,origMap.get(ch)+1);
            }else{
                origMap.put(ch,1);
            }
        }
        // if a char in S are find in T, if enough apperarance of char, we put it in findMap, otherwise put in totalMap
        for(int i =0;i<S.length();i++){
            char ch = S.charAt(i);
            if(origMap.containsKey(ch) == false)
                continue;
            int count = origMap.get(ch);
            if(findMap.containsKey(ch)){
                findMap.put(ch,findMap.get(ch)+1);
            }else{
                if(totalMap.containsKey(ch)){
                    totalMap.put(ch,totalMap.get(ch)+1);
                }else{
                    totalMap.put(ch,1);
                }
                // check if enough appearance
                if(totalMap.get(ch)>=origMap.get(ch)){
                    findMap.put(ch,totalMap.get(ch));
                    totalMap.remove(ch);
                }
            }
            // check whether we can shrink
            while(findMap.size()==origMap.size()){// find a match, and begin to shrink
                char newChar = S.charAt(start);
                if(origMap.containsKey(newChar)){
                    if(findMap.get(newChar) == origMap.get(newChar)){ // begin to delete
                        totalMap.put(newChar,findMap.get(newChar)-1);
                        if(minEnd - minStart > i - start){
                            minStart = start;
                            minEnd = i;
                        }
                        findMap.remove(newChar);
                    }else{
                        findMap.put(newChar,findMap.get(newChar)-1);
                    }
                }
                start++;
            }
        }
        return minStart==S.length()?"":S.substring(minStart,minEnd+1);
    }
}

---------------3 rd Pass -------------不错不错， 方法虽然是新的idea，但是， 只改了几个拼写错误 ， 然后，就一遍过了 --------  哎，Tiger，有进步阿-------------------

IDEA：
用一个HashSet记录是不T 中出现过的字母。 （其实可以用查询MapT,usedMap来代替的,为了清晰，我们这里还是用了）
然后，用一个HashMap， 记录出现字母在T中的次数。 以及发现了的次数。
然后，如果全部发现的话，就把这个对象放进另一个HashMap中缓存起来（当然，如果再次发现的话，也要在这个缓存的Map中更新 nFind。

public class Solution {
    public String minWindow(String S, String T) {
        String result = null;
        // IDEA: use to map to count the strings , if for a char, all are used,
        // Note that duplicates in T are also counted
        // build HashMap for T
        HashMap<Character, Node> mapT = new HashMap<Character, Node>();
        HashSet<Character> set = new HashSet<Character>();
        HashMap<Character, Node> usedMap = new HashMap<Character, Node>();
        for (int i = 0; i < T.length(); i++) {
            char ch = T.charAt(i);
            if (mapT.get(ch) == null) {
                Node tmp = new Node();
                mapT.put(ch, tmp);
                set.add(ch);
            } else {
                mapT.get(ch).count++;
            }
        }
        int begin = 0;// begin of current sub window
        for (int i = 0; i < S.length(); i++) {
            char ch = S.charAt(i);
            if (!set.contains(ch)) { // not in the T String
                continue;
            }

            Node tmp = mapT.get(ch);
            if (tmp == null) {// should be in usedMap,
                tmp = usedMap.get(ch);
                tmp.nFind++;
            } else {// ch appeared in mapT, then we need check
                tmp.nFind++;
                if (tmp.count == tmp.nFind) { // all appearance have been found
                    mapT.remove(ch);
                    usedMap.put(ch, tmp);
                }
            }
            // check whether we should shrink, and from beginning
            while (mapT.isEmpty()) {
                if (result == null || result.length() > i - begin + 1) {
                    result = S.substring(begin, i + 1);
                }
                char tmpChar = S.charAt(begin);
                begin++;
                if (set.contains(tmpChar)) {
                    Node tmpNode = usedMap.get(tmpChar);
                    if (tmpNode.nFind == tmpNode.count) {
                        usedMap.remove(tmpChar);
                        mapT.put(tmpChar, tmpNode);
                    }
                    tmpNode.nFind--;
                }
            }
        }
        return result == null ? "" : result;
    }
}

class Node {
    public int count, nFind;// count if char, and number of find char

    public Node() {
        count = 1;
        nFind = 0;
    }
}