MinWindow.java

public class Solution {
    public String minWindow(String S, String T) {
        if (S.length() == 0) return "";
        
        Map<Character, Integer> expected = new HashMap<Character, Integer>();
        Map<Character, Integer> actual = new HashMap<Character, Integer>();
        populateMap(expected, T);

        int start = 0, next = 0;
        int bestStart = 0, bestEnd = Integer.MAX_VALUE;
        int count = 0;
        while(next < S.length()) {
            char c = S.charAt(next);
            if (expected.containsKey(c)) {
                if (!actual.containsKey(c)) actual.put(c, 0);
                actual.put(c, 1+actual.get(c));
                if (actual.get(c) <= expected.get(c)) count++;
            }
            while(count == T.length()) {
                if (bestEnd-bestStart>next-start) {
                    bestEnd = next; bestStart = start;
                }
                char head = S.charAt(start);
                if (expected.containsKey(head)) {
                    actual.put(head, actual.get(head)-1);
                    if (actual.get(head) < expected.get(head)) count--;
                }
                start++;
            }
            next++;
        }
        if (bestEnd-bestStart > S.length()-1) return "";
        else return S.substring(bestStart, bestEnd+1);
    }
    
    private void populateMap(Map<Character, Integer> expected, String s) {
        if (s == null) return;
        for(char c: s.toCharArray()) {
            if (!expected.containsKey(c)) expected.put(c, 0);
            expected.put(c, 1+expected.get(c));
        }
    }
}