Minimum Window Substring

题目地址：
https://leetcode.com/problems/minimum-window-substring/#/description

题目：

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 empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

解题思路：
这道题是substring的问题，这一类问题可以有一个模板可以套。refered from: https://discuss.leetcode.com/topic/30941/here-is-a-10-line-template-that-can-solve-most-substring-problems

String findSubstring(String s, String t){
    Map<Character, Integer> map = new HashMap<>();

    int count; // check whether the substring is valid    int left=0, right=0; //two pointers, one point to tail and one  head    int minLen = s.length() + 1; //the length of substring    int minLeft = 0; // the left boundary of the substring
    for() { /* initialize the hash map here */ }

    for(right = 0; right <= s.length(); right++){
        char curr = s.charAt(right);
        if(map.containsKey(curr)){
            /* update map and modify count here if necessary */
            while(/* count meets the condition */){

                /* update minLeft and minLen here if finding minimum*/
                char leftChar = s.charAt(minLeft);

                //increase begin to make it invalid/valid again                if(map.containsKey(leftChar)){
                    /*modify counter here*/                }
                left++;
            }
        }
    }
    if(minLen > s.length()){
        return "";
    }
    
    return s.substring(minLeft, minLen);
}

代码：

public String minWindow(String s, String t) {
    if(s == null || s.length() < t.length() || s.length() == 0){
        return "";
    }
    Map<Character, Integer> map = new HashMap<>();
    for(char c : t.toCharArray()){
        if(map.containsKey(c)){
            map.put(c, map.get(c) + 1);
        }
        else{
            map.put(c, 1);
        }
    }
    int left = 0;
    int right = 0;
    int minLeft = 0;
    int minLen = s.length() + 1;
    int count = 0;
    for( ; right <= s.length() - 1; right++){
        char curr = s.charAt(right);
        if(map.containsKey(curr)){
            map.put(curr, map.get(curr) - 1);
            if(map.get(curr) >= 0){
                count++;
            }
            while(count == t.length()){
                if(right - left + 1 < minLen){
                    minLen = right - left + 1;
                    minLeft = left;
                }
                char leftChar = s.charAt(left);
                if(map.containsKey(leftChar)){
                    map.put(leftChar, map.get(leftChar) + 1);
                    if(map.get(leftChar) > 0){
                        count--;
                    }
                }
                left++;
            }
        }
    }
    if(minLen > s.length()){
        return "";
    }
    return s.substring(minLeft, minLeft + minLen);
}