76. Minimum Window Substring

    /*
     * 76. Minimum Window Substring 
     * 12.1 by Mingyang
     * http://blog.csdn.net/linhuanmars/article/details/20343903 
     * 同样用hashmap存
     * 其实主要思路就是维护一个窗口，最开始left为0，右边为第一次包含所有需要的string的位置，
     * 然后更新left到第一个有效的位置
     * 计算出之间的距离，然后继续右边界往前走，
     * 走到下一个满足条件的右边界，然后进行新一轮的计算最小距离 S为大的，T为小的
     * 对这个题目最好的例子就是CDAAAAAABC   S为ABC
     */
    public String minWindow(String S, String T) {
        if (S == null || S.length() == 0)
            return "";
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < T.length(); i++) {
            if (map.containsKey(T.charAt(i))) {
                map.put(T.charAt(i), map.get(T.charAt(i)) + 1);
            } else {
                map.put(T.charAt(i), 1);
            }
        }
        int left = 0;
        int count = 0;
        int minLen = S.length() + 1;
        int minStart = 0;
        for (int right = 0; right < S.length(); right++) {
            // 如果map中存在的话。就把那个值减一，每加一个有效值，count就加加。当有效值达到T的长度的时候，就可以验证是否可以移动窗户了
            // 不过移动前先更新一下窗户的大小，也就是minLen的值
            // 那么如果没有窗户最左边的那个值，直接移动，如果最左边那个值为有效值，那么移动以后count要减一，这样右边又要继续走→_→
            if (map.containsKey(S.charAt(right))) {
                map.put(S.charAt(right), map.get(S.charAt(right)) - 1);
                if (map.get(S.charAt(right)) >= 0) {
                    count++;
                }
                while (count == T.length()) {// 表明已经有窗口框住了所有有效值的时候
                    if (right - left + 1 < minLen) {
                        minLen = right - left + 1;
                        minStart = left;
                    }// 计算一次
                    if (map.containsKey(S.charAt(left))) {
                        map.put(S.charAt(left), map.get(S.charAt(left)) + 1);
                        if (map.get(S.charAt(left)) > 0) {
                            count--;
                        }
                    }
                    left++;
                }
            }
        }
        if (minLen > S.length()) {
            return "";
        }
        return S.substring(minStart, minStart + minLen);
    }