[LintCode/LeetCode] 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 "".

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

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

Not necessary.

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

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

public class Solution {
    public String minWindow(String source, String target) {
        int[] S = new int[255], T = new int[255];
        for (int i = 0; i < target.length(); i++) T[target.charAt(i)]++;
        int start = 0, left = -1, right = source.length(), match = 0, len = source.length();
        for (int i = 0; i < source.length(); i++) {
            S[source.charAt(i)]++;
            if (S[source.charAt(i)] <= T[source.charAt(i)]) match++;
            if (match == target.length()) {
                while (start < i && S[source.charAt(start)] > T[source.charAt(start)]) {
                    S[source.charAt(start)]--;
                    start++;
                }
                if (i - start < len) {
                    len = i - start;
                    left = start;
                    right = i;
                }
                S[source.charAt(start)]--;
                match--;
                start++;
            }
        }
        return left == -1 ? "" : source.substring(left, right+1);
    }
}

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) return "";
        int[] dict = new int[256];
        for (char ch: t.toCharArray()) {
            dict[ch]++;
        }
        int l = 0, r = 0, start = -1;
        int count = t.length();
        int min = Integer.MAX_VALUE;
        while (r < s.length()) {
            char ch = s.charAt(r);
            if (dict[ch] > 0) count--;
            dict[ch]--;
            r++;
            
            while (count == 0) {
                ch = s.charAt(l);
                if (dict[ch] == 0) count++;
                dict[ch]++;
                if (r-l < min) {
                    min = r-l;
                    start = l;
                }
                l++;
            }
        }
        return start == -1 ? "" : s.substring(start, start+min);
    }
}