76. 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).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

---

给两个字符串S和T，问S中是否存在一个子串，包括T中的所有字符，如果存在，输出最短的那个子串。

hard题，用双指针+滑动窗口。核心思想是找到滑动窗口[i,j)，首先++j，加入右边界的字符；然后检查[i,j)是否能覆盖t；再然后++i，丢掉左边界的字符。

首先设置一个required数组，存储t中每个字符出现的次数，表示滑动窗口[i,j)需要覆盖的每个字符的次数。found表示需要找到的字符总数，如果found==t.size()表示滑动窗口能覆盖t。

首先检查右边界j，如果s[j]在t中，则++found。然后看看found==n?，如果是，则检查左边界，如果左边界s[i]在t中，则i++之后要–found。在窗口滑动过程中记录窗口最小长度。完整代码如下：

class Solution {
public:
	string minWindow(string s, string t) {
		int m = s.size(), n = t.size();
		vector<int> required(128, 0);
		for (int i = 0; i < n; ++i) {
			++required[t[i]];
		}

		int min_len = m + 1, start_id = 0, found = 0;
		int i = 0, j = 0;
		while (j < m) {
			--required[s[j]];
			if (required[s[j]] >= 0) { // s[j]在t中
				++found;
			}
			++j;

			while (found == n) {
				int cur_len = j - i;
				if (cur_len < min_len) {
					min_len = cur_len;
					start_id = i;
				}
				++required[s[i]];
				if (required[s[i]] > 0) --found;
				++i;
			}
		}
		if (min_len == m + 1) return "";
		else return s.substr(start_id, min_len);
	}
};

本代码提交AC，用时16MS。

今晚字节跳动三面，面试官问了一个此题的变种，即只给定了字符串s，要找s的一个子串，使得该子串能覆盖s中所有特异的字符，且子串越短越好。可以把面试问题转换为这个问题，即先遍历s，把s中的特异字符拼成一个字符串t，然后调用本题的解法。