Minimum Window Substring

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

Notice

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.

Clarification

Should the characters in minimum window has the same order in target?

--> Not necessary.

Example

For source = "ADOBECODEBANC", target = "ABC", the minimum window is "BANC"

Notes:

1. Forward two pointers
2. Apply template
3. Condition: use HashMap to judge contains or not
4. Time: O(n*m)

    public String minWindow(String source, String target) {
        if (source == null || source.isEmpty() || target == null || target.isEmpty()) {
            return "";
        }

        Map<Character, Integer> sourceMap = new HashMap<>();
        Map<Character, Integer> targetMap = initializeTarget(target);

        int n = source.length();
        int j = 0;
        String min = "";

        for (int i = 0; i < n; ++i) {
            while(j < n && !contains(sourceMap, targetMap)) {
                char c = source.charAt(j);
                if (!sourceMap.containsKey(c)) {
                    sourceMap.put(c, 1);
                } else {
                    sourceMap.put(c, sourceMap.get(c)+1);
                }
                j++;
            }

            if (contains(sourceMap, targetMap)) {
                String substring = source.substring(i, j);
                if (min.isEmpty() || min.length() > substring.length()) {
                    min = substring;
                }
            }

            int num = sourceMap.get(source.charAt(i));
            if (num > 1) {
                sourceMap.put(source.charAt(i), num-1);
            } else {
                sourceMap.remove(source.charAt(i));
            }
        }

        return min;
    }

    private Map<Character, Integer> initializeTarget(String target) {
        Map<Character, Integer> targetMap = new HashMap<>();
        int size = target.length();
        for (int i = 0; i < size; ++i) {
            char c = target.charAt(i);
            if (!targetMap.containsKey(c)) {
                targetMap.put(c, 1);
            } else {
                targetMap.put(c, targetMap.get(c)+1);
            }
        }

        return targetMap;
    }

    private boolean contains(Map<Character, Integer> sourceMap, Map<Character, Integer> targetMap) {
        if (sourceMap.isEmpty()) {
            return false;
        }

        for (char c : targetMap.keySet()) {
            if (!sourceMap.containsKey(c)) {
                return false;
            }

            if (targetMap.get(c) > sourceMap.get(c)) {
                return false;
            }
        }

        return true;
    }