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).

Example:

Input: S = "ADOBECODEBANC", 
T = "ABC"
Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string "" .
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null) {
            return "";
        }
        if (s.length() < t.length()) {
            return "";
        }
        int start = 0;
        int end = 0;
        int from = 0;

        int minLen = Integer.MAX_VALUE;
        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 count = map.size();
        while (end < s.length()) {
            char temp = s.charAt(end);
            if (map.containsKey(temp)) {
                map.put(temp, map.get(temp) - 1);
                if (map.get(temp) == 0) {
                    count--;
                }
            }
            end++;
            while (count == 0){
                char tempc = s.charAt(start);
                if (map.containsKey(tempc)) {
                    map.put(tempc, map.get(tempc) + 1);
                    if (map.get(tempc) > 0) {
                        count++;
                    }    
                }
                if (end - start < minLen) {
                    minLen = end - start;
                    from = start;
                }
                start++;
            }
        }
        if (minLen == Integer.MAX_VALUE) {
            return "";
        }
        return s.substring(from, from + minLen);
    }
}