76. Minimum Window Substring.md

76. Minimum Window Substring

思路

给定字符串S和T，要在S中找到一个最短的子串，使得其包含了T中的所有的字母，并且限制时间复杂度为 O(n)。

由于限制时间复杂度为O(n)，所以我最开始想到的思路是双指针法，用两个指针 l 和 r 从S的两端分别向中间缩小，但是发现这样得出的子串不一定就是最小的。

看了答案发现也是用双指针，不过不是从两端往中间缩小，而是都从最左边开始，先将 r 不断右移以扩大窗口直到包含了T的所有字符，然后在包含T中所有字符的前提下尝试将 l 不断右移缩小窗口。这样一伸一缩后就是求得了当前最小的一个子串，然后再用同样的思路将两个指针向右滑动，用一个全局变量记录整个过程的最短长度。

我们可以用一个长度为128（ASCII码为0-127）的整型数组 cnt 来记录T串每个字符的出现次数，然后还需要用一个变量 win_cnt 来记录在窗口中的包含在T中的字符数，这样如果 win_cnt == T.size()就说明找到了满足条件的子串，更新全局变量的最短长度和起始位置。

需要特别注意 win_cnt 的更新方式，当某个字符c进入窗口时，只有当--cnt[c] >= 0时才使 cnt 加1；同理，当某个字符 c 离开窗口时，只有当++cnt[c] > 0时才使 cnt 减 1。

时间复杂度O(m+n)

C++

class Solution {
public:
    string minWindow(string s, string t) {
        int sn = s.size(), tn = t.size();
        vector<int>cnt(128, 0);
        for(int i = 0; i < tn; i++) cnt[t[i]]++;
        
        int win_cnt = 0;
        int l = 0, smallest_l = -1, smallest = INT_MAX;
        for(int r = 0; r < sn; r++){
            if(--cnt[s[r]] >= 0) win_cnt++;
            
            while(win_cnt == tn){
                if(smallest > r - l + 1){
                    smallest = r - l + 1;
                    smallest_l = l;
                }
                if(++cnt[s[l]] > 0) win_cnt--;
                l++;
            }
        }
        
        return smallest_l == -1 ? "" : s.substr(smallest_l, smallest);
    }
};