题目

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”

解法

这道题目，我一开始用动态规划做，感觉有点难哦，只能看答案。
讨论区有个人给了一个解决一类字符串问题的模板:

For most substring problem, we are given a string and need to find a substring of it which satisfy some restrictions. A general way is to use a hashmap assisted with two pointers. The template is given below.

int findSubstring(string s) {
    vector<int> map(128,0);
    int counter; // check whether the substring is valid
    int begin=0, end=0; //two pointers, one point to tail and one  head
    int d; //the length of substring

    for() { /* initialize the hash map here */ }

    while(end<s.size()){

        if(map[s[end++]]-- ?){  /* modify counter here */ }

        while(/* counter condition */){

             /* update d here if finding minimum*/

            //increase begin to make it invalid/valid again

            if(map[s[begin++]]++ ?){ /*modify counter here*/ }
        }  

        /* update d here if finding maximum*/
    }
    return d;
}

这个模板暗示的算法是，维护两个指针start和end分别指向子串的起始位置和结束位置，end向后遍历，当满足子串的性质之后，
向后移动start破坏该性质并寻找下一个满足性质的位置。

用这个思想可以解决Longest Substring Without Repeating Characters

代码

string minWindow(string s, string t) {
  int ascii[256];
  memset(ascii, 0, 256 * sizeof(int));
  int count = 0;
  for (int i = 0; i < t.length(); i++) {
      ascii[t[i]]++;
      count++;
  }

  int start = 0, end = 0;
  int minLen = 999999, minStart = 0;
  while (end < s.length()) {
      if (ascii[s[end]]-- > 0) {
          count--;
      }
      while (count == 0) {
          if (end - start + 1 < minLen) {
              minStart = start;
              minLen = end - start + 1;
          }
          if (++ascii[s[start++]] > 0) {
              count++;
          }
//            if (start > end) break;
      }
      end++;
  }
  if (minLen == 999999 ) return "";
  return s.substr(minStart, minLen);
}