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 empty string"".

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

Subscribe to see which companies asked this question.

給出了；兩個字符串s和t，求s中包含t所有字符的最短的子字符串。要注意的是t中的字符可能是重復的。這里使用兩個索引left和right指定符合條件的子字符串的開頭和結尾。首先對right自增，直到t中的所有字符都有了。因為有重復的字符，所以用map來記錄好重復次數，當所有次數都滿足時停止right的增長。現在s[left, right]已經是符合要求的子字符串。為了求最短的，將left增長，直到剛好有一個字符的數量不滿足次數要求，現在的s[left, right]就是當前最短的答案。然后又將right增長，求另外的有可能的答案。。。最后返回最短的答案即可。

代碼：

class Solution{public:	string minWindow(string s, string t) 	{		int cnt[256] = {0}, map[256] = {0};		int types = 0, left = 0, right = 0, n = 0, len = INT_MAX;		string res;		for(auto c:t) 		{			if(map[c]++ == 0) n++;		}		while(right < s.size())		{			while(right < s.size() && types < n)			{				if(map[s[right]] > 0 && ++cnt[s[right]] == map[s[right]])				{					++types;				}				++right;			}			if(types < n) break;			while(left < right)			{				if(map[s[left]] > 0 && --cnt[s[left]] < map[s[left]])				{					--types;					break;				}				++left;			}			if(right - left < len)			{				len = right - left;				res = s.substr(left, right-left);			}			++left;		}		return res;	}};
在別人的答案中看到一個號稱是最短的答案，挺不錯的：
string minWindow(string s, string t) {        vector<int> map(128,0);        for(auto c: t) map[c]++;        int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0;        while(end<s.size()){            if(map[s[end++]]-->0) counter--; //in t            while(counter==0){ //valid                if(end-begin<d)  d=end-(head=begin);                if(map[s[begin++]]++==0) counter++;  //make it invalid            }          }        return d==INT_MAX? "":s.substr(head, d);    }