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，然后调用本题的解法。