给定两个串，S和T，在S中找到包含T的最短子串，如果不能包含，返回空字符。
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.
这题了好久，暴力解决的话要n方，所以没去尝试。
后来参考了这位。自己也敲了敲代码。算是弄懂了，在代码中加了些注释。
可以利用两个指针扫描（两个指针分别为start，i），以S = “e b a d b a c c b”（忽略空格），T = “abc”为例：
0 1 2 3 4 5 6 7 8
具体实现时，要用哈希表来映射T中字符以便在O(1)时间内判断一个字符是否在T中，由于是字符缘故，可以用数组简单的来实现；还需要一个哈希表来记录扫描时T中的某个字符在S中出现的次数，也可以用数组实现
class Solution { public: string minWindow(string S, string T) { int lens = S.size(), lent = T.size(); int Tcnt[256] = {0}; int Scnt[256] = {0}; for (int i = 0; i < lent; i++) { Tcnt[T[i]]++; // 记录T中的字符以及次数 } int hasfound = 0; int start = 0; int swin = -1, ewin = lens; for (int i = 0; i < lens; i++) { if (Tcnt[S[i]]) // 如果T中存在S[i]，那么要进行一下判断是否有窗口符合 { Scnt[S[i]]++; // 记录窗口中字符次数 if (Scnt[S[i]] <= Tcnt[S[i]]) hasfound++; // 如果次数满足小于等于T中的，就找到一个数 if (hasfound == lent) // 说明找到一个符合条件窗口 { // 缩减 while(Tcnt[S[start]] == 0 || Scnt[S[start]] > Tcnt[S[start]]) { if (Tcnt[S[start]] != 0)//说明是||右边的符合 Scnt[S[start]]--; start++; } if (ewin - swin > i - start) { ewin = i; swin = start; } //记录开始结束之后start继续前移 Scnt[S[start]]--; start++; hasfound--; // 因为start往前移动了，所以少一个已经找到的数 } } } return swin == -1 ? "" : S.substr(swin, ewin - swin + 1); } };
leetcode[76] Minimum Window Substring
原文：http://www.cnblogs.com/higerzhang/p/4100898.html