Minimum Window Substring

• https://leetcode.com/problems/minimum-window-substring/

Similar problems: https://leetcode.com/problems/substring-with-concatenation-of-all-words/

Solution: two pointers to maintain a window.

• http://blog.csdn.net/linhuanmars/article/details/20343903

• http://blog.csdn.net/linhuanmars/article/details/20342851

public String minWindow(String s, String t) {
    if (s == null || s.length() == 0) return "";
    Map<Character, Integer> map = new HashMap();

    // construct a map with character in T and its occurence.
    for (int i = 0; i < t.length(); i++) {
        if (!map.containsKey(t.charAt(i))) {
            map.put(t.charAt(i), 1);
        } else {
            map.put(t.charAt(i), map.get(t.charAt(i)) + 1);
        }
    }

    int left = 0; // left pointer
    int minLength = s.length() + 1; // length of the minimum substring
    int minStart = 0; // start point of the minimumn substring
    int count = 0; // number of the elements meet so far

    for (int right = 0; right < s.length(); right++) {
        // when we meet a character in T
        if (map.containsKey(s.charAt(right))) {
            // reduce the number in the map by 1
            map.put(s.charAt(right), map.get(s.charAt(right)) - 1);
            if (map.get(s.charAt(right)) >= 0) { // only count when we have meet the elements we want.
                count++;
            }

            while (count == t.length()) {// when we found a substring contains T
                if (right - left + 1 < minLength) {
                    minLength = right - left + 1;
                    minStart = left;
                }

                // if the s.charAt(left) is the character in T
                // add 1 to the map, and do count-- to find the next substring
                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 (minLength > s.length()) return "";
    return s.substring(minStart, minStart + minLength);

}