76. Minimum Window Substring

problem description

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.

algorithm thought

滑动窗口问题，做了很多题目之后，碰到最后需要求连续序列满足一种情况的时候，一般都能用滑动窗口，也就是一前一后指针代表窗口。

这里首先定义一个vector，存储所有字符出现的次数。然后定义一前一后两个指针，后指针走过一个字符的时候，将vector中字符保存的次数减一，如果减一是有效的（能在T字符串中体现），那就将之前保存的size减一(size 初始化是T.size())。如果size为0，就可以将当前状态加入到结果。并且移动头指针，逼近尾指针。

code

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> map(128,0);
        for(auto c:t)
            map[c]++;
        int  begin=0,end=0,head=0,length=INT_MAX;
        int count=t.size();
        while(end<s.size()){
            if(map[s[end++]]-->0) count--;
            while(count==0){
                if(length>end-begin) length=end-(head=begin);
                if(map[s[begin++]]++>=0) count++; 
            }
        }
        return length==INT_MAX?"":s.substr(head,length);
    }
};

algorithm analysis

滑动窗口时间复杂度O(n),只需要一次遍历数组，最后产生结果。