Given a string source and a string target, find the minimum window in source which will contain all the characters in target.

Example

source = "ADOBECODEBANC" target = "ABC" Minimum window is "BANC".

Note

If there is no such window in source that covers all characters in target, return the emtpy string "".

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

Challenge

Can you do it in time complexity O(n) ?

Clarification

The characters in minimum window doesn't need to has the same order in target.

Solution:

    public String minWindow(String source, String target) {
        // preload for target checking
        if(source == null || source.length() == 0 || target == null || target.length() == 0)
            return "";


        int tarLen = target.length();
        HashMap<Character, Integer> dict = new HashMap<>();
        for(char c : target.toCharArray()) 
            dict.put(c, dict.containsKey(c)? dict.get(c) + 1 : 1);

        int hitCount = 0; // record current window hits how many characters in target
        int prevIdx = 0; // record the left bound of current window
        int minWindow = source.length() + 1; // initial the minimum window length
        int start = 0;
        for(int i = 0; i < source.length(); i++) {
            char cur = source.charAt(i);
            // if current char is not in dict, continue
            if(!dict.containsKey(cur))
                continue;

            dict.put(cur, dict.get(cur) - 1);
            if(dict.get(cur) >= 0)
                hitCount++;

            // check the windows has amount of this char more than it in target string
            // loop until the amount back to normal, but always reduce the prev index char
            while(hitCount == tarLen) {
                if( minWindow > i - prevIdx + 1) {
                    start = prevIdx;
                    minWindow = i - prevIdx + 1;
                }
                char prevChar = source.charAt(prevIdx);
                if(dict.containsKey(prevChar)) {
                    dict.put(prevChar, dict.get(prevChar)+1);
                    if(dict.get(prevChar) > 0)
                        hitCount--;
                }
                prevIdx++;
            }
        }
        // 
        if(minWindow > source.length())
            return "";
        return source.substring(start, start + minWindow);
    }