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. If there is no such window in source that covers all characters in target, return the emtpy string "".

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"

Solution:

We could find the frequency of characters in target and find the same patten in source by using the Sliding Window Two Pointers. However, we would like to use for loop as the right pointer and while loop as the left pointer (to catch up the right).

If a character in source is also appeared in target (this could be done by checking the frequency of characters in target), we need to increase sourceNum by one. This sourceNum is used to indicate all characters in target are found (when sourceNum = target.length()), left could start to catch up and to find the minimum window.

Code:

public class Solution {
    /**
     * @param source: A string
     * @param target: A string
     * @return: A string denote the minimum window
     *          Return "" if there is no such a string
     */
    public String minWindow(String source, String target) {
        if (source == null || target == null || 
                                source.length() == 0 || target.length() == 0) {
            return "";
        }
        int n = source.length();
        int m = target.length();
        int[] targetCount = new int[256];
        for (int i = 0; i < m; i++) {
            targetCount[target.charAt(i)]++;
        }
        int j = 0;
        int len = Integer.MAX_VALUE;
        int start = 0;
        int end = 0;
        int sourceNum = 0;
        for (int i = 0; i < n; i++) {
            if (targetCount[source.charAt(i)] > 0) {
                sourceNum++;
            }
            targetCount[source.charAt(i)]--;
            while (sourceNum >= m) {
                if (len > i - j + 1) {
                    len = i - j + 1;
                    start = j;
                    end = i;
                }
                targetCount[source.charAt(j)]++;
                if (targetCount[source.charAt(j)] > 0) {
                    sourceNum--;
                }
                j++;
            }
        }
        return source.substring(start, end + 1);
    }
}