学步园

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:

If there is no such window in S that covers all characters in T, return the emtpy string "".

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

这题需要设置双指针，一个作为所求window substring的开始处下标start，一个作为所求window substring的结束处下标end。两个下标最开始都指向S[0]。移动过程如下：

1）向前移动end，伸展window substring，直到该子字符串完全覆盖T；

2）向前移动start，收缩window substring，直到该子字符串刚好完全覆盖T。

这样得到的一个window substring的长度具有极小值，是所求全局最短子字符串的一个candidate。

重复以上两步，获得更多的candidate，不断更新全局最短子字符串，直到end越出S的右边界。

注意题目这里有点没说明确，如果一个字符在T中重复了N次，那么所求的子字符串内也必须让该字符重复出现N次。本来一开始用了HashSet，后来发现不光要记录一个字符是否在T中出现，并且还得记录出现的次数，所以后来换成了HashMap，key和value是T里出现的字符和次数。一开始做了个word count。（让人不禁联想到了MapReduce，汗~）

为了判断子字符串是否覆盖T，维护了一个计数器，每找到一次字符匹配，就加1，直到等于T的字符串长度，但是匹配一旦超过了T本身含有的该字符，就不再追加。

	public String minWindow(String S, String T) {
		boolean found = false;
		String ret = S;
		String curStr;
		// record the character frequencies for T
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		for (int i = 0; i < T.length(); i++) {
			char c = T.charAt(i);
			if (map.containsKey(c)) {
				map.put(c, map.get(c) + 1);
			} else {
				map.put(c, 1);
			}
		}

		int start = 0, end = 0, count = 0;
		// in order to cover T, extend the current string by moving the end forward
		while (end < S.length()) {
			char cEnd = S.charAt(end);
			if (map.containsKey(cEnd)) {
				// the # of this character unmatched in T
				int num1 = map.get(cEnd);
				num1--;
				map.put(cEnd, num1);
				if (num1 >= 0) {
					count++;
					// if T can be covered by the current substring
					while (count == T.length()) {
						found = true;
						// shrink the current substring by moving the start forward
						char cStart = S.charAt(start);
						if (map.containsKey(cStart)) {
							// the # of this character unmatched again in T
							int num2 = map.get(cStart);
							num2++;
							map.put(cStart, num2);

							// not covered again
							if (num2 > 0) {
								count--;
								curStr = S.substring(start, end + 1);
								if (curStr.length() < ret.length()) {
									ret = curStr;
								}
							}
						}
						start++;
					}
				}
			}
			end++;
		}

		if (found)
			return ret;
		else
			return "";
	}