Problem

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"

Challenge

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

Note

之前居然没有做过，惭愧。

找出给定字符串source中包含目标字符串target的最短子串，怎么做？
建立对应给定串的hash数组S，对应目标串的hash数组T，大小都是255，别问我怎么知道的：总共有255个字符啊。
建立循环，遍历整个给定串source：用start作为标记开始点的指针，不断更新从start到当前点i的子串范围，并用len(=i-start)标记当前最小子串的长度，再用match标记已经找到的source和target匹配的字符数，以及，用left和right两个指针标记当前子串的边界。

循环中，每个遍历到的字符，在数组中对应的位置S[source.charAt(i)]进行+1操作。
这个S中的字符，在T中也对应同一位。如果这个字符在S中的数值，相对应的，小于等于T中的数值，就说明这一位是source和target中是可以匹配的，所以match加1。

当match和目标串target长度相等时，是不是意味着我们在source中找到了一个符合题意的window substring呢？是的，这是一个坐标从start到i的子串。
而且，这个子串的头部也许会有一些多余的字符，判断这些字符的方法是，它们在hash数组S中的数值一定大于在T中的数值。我们就以start为指针找到这些字符，并将它们在S中的值进行-1的操作，直到子串的头部不再有多余的字符，即source中第start个字符在S和T中的值相等的时候。

然后，我们看这个子串的长度是否比之前求得的子串的最小长度len更短。如果是，那么这个子串才是最小的window substring，我们就更新子串的边界left和right。
在更新边界之后，这个解就可以功成身退了。因此，我们将start加1，同时将match的数目减1，进入下一个循环继续求解。

最后，视左边界left是否仍为-1，以返回空解""或以left和right围成区间的子串。

Solution

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);
    }
}