(每日算法)LeetCode---Minimum Window Substring (最小子串窗口)

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.

/*
* 整个思想就是双指针，动态维护一个区间。尾指针不断往后扫，当扫到有一个窗口包含了所有T的字符后，
*然后再收缩头指针，直到不能再收缩为止。最后记录所有可能的情况中窗口最小的.
*使用appreared_count[]存储S中实时段上相应字符出现的次数，expected_count[]用来存储T中字符出现的次数。
*首先威志针向后移动一位，如果该位上的字符出现在T中，那么就在appreared_count[]中加上该字符。
*同时，如果该字符在appreared_count[]中出现的次数低于expected_count[]出现的次数，也就是说明
*当前还没有完全包含T,因此appreared_count ++,它用来统计T的大小来保证T 被完全包含。
*接下来---如果T已经被完全包含，那么就可以考虑收缩头指针了。
*如果头指针（wnd_start）所指向的元素是冗余的，那么头指针就可以向前移动一位。
*当然，如果当前的头指针是expected_count[]没出现过的，也要向前移动一位，这里出现负数没有关系。
*接下来循环上述步骤，尽量的压缩头指针。
*wnd_start和wnd_end之间就是我们相求的结果，用变量minWidth保存他们之间的长度，如果尾指针后移一位以后，
*引起头指针有效的收缩，那么minWidth就会减小。这个时候保存新的头指针的位置。
*/
string minWindow(string S, string T) {
	if (S.empty()) return "";
	if (S.size() < T.size()) return "";
	const int ASCII_MAX = 256;
	int appeared_count[ASCII_MAX];
	int expected_count[ASCII_MAX];
	fill(appeared_count, appeared_count + ASCII_MAX, 0);
	fill(expected_count, expected_count + ASCII_MAX, 0);
	for (size_t i = 0; i < T.size(); i++) expected_count[T[i]]++;
	int minWidth = INT_MAX, min_start = 0; // 窗口大小，起点
	int wnd_start = 0;
	int appeared = 0; // 完整包含了一个T
	//尾指针不断往后扫
	for (size_t wnd_end = 0; wnd_end < S.size(); wnd_end++) {
		if (expected_count[S[wnd_end]] > 0) { // this char is a part of T
			appeared_count[S[wnd_end]]++;
			if (appeared_count[S[wnd_end]] <= expected_count[S[wnd_end]])
				appeared++;
		}
		if (appeared == T.size()) { // 完整包含了一个T
			// 收缩头指针
			while (appeared_count[S[wnd_start]] > expected_count[S[wnd_start]] || expected_count[S[wnd_start]] == 0) {
				appeared_count[S[wnd_start]]--;
				wnd_start++;
			}
			if (minWidth > (wnd_end - wnd_start + 1)) {
				minWidth = wnd_end - wnd_start + 1;
				min_start = wnd_start;
			}
		}
	}
	if (minWidth == INT_MAX) return "";
	else return S.substr(min_start, minWidth);
};