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"

代码论坛里找的，写的太巧妙了，我是写不出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public String minWindow(String s, String t) {
    int[] map = new int[128];
    for (int i = 0; i < t.length(); i++) {
        map[t.charAt(i)]++;
    }
    int counter = t.length();
    int i = 0, j = 0;
    int start = 0;
    int d = Integer.MAX_VALUE;
    while (j < s.length()) {
        if (map[s.charAt(j++)]-- > 0)
            counter--;
        while (counter == 0) {
            if (j - i < d) {
                start = i;
                d = j - i;
            }
            if (map[s.charAt(i++)]++ == 0)
                counter++;
        }
    }
    return d == Integer.MAX_VALUE ? "" : s.substring(start, start + d);
}