076 - Minimum Window Substring

Minimum Window Substring

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.

Hide Tags

Hash Table Two Pointers String

Hide Similar Problems

(H) Substring with Concatenation of All Words (M) Minimum Size Subarray Sum (H) Sliding Window Maximum

 

这题做得折腾。。。

一开始全然没有意识到它跟之前做的209 - Minimum Size Subarray Sum的联系，

整了个比较naive的思路，用hash表保存t里头的字符以及它在 s 中最新的下标，

却没有料到test case里t还有重复的字符……郁闷

只好把hash表的value从int变成了vector<int>，第一个值存数量，而后存它在 s 中的各个下标

但是超时~~

 

跑去翻看题解，只看了一行字NND差点撞墙，刚做的209啊！！重写吧，还是七上八下，惭愧。

首先是怎么检测 s 中已经走到的部分是否包含了 t 的全部字母的方法低效，造成超时；

（因为 t 里有重复的，所以比较愚蠢地把 s.substr 排序再查找排过序的 t，效率不言而喻…）

再去看题解的代码，两个数组就解决问题了…，换算数组再重写吧。

结果还遇到一个问题，就是原来写209的时候，从零开始找到第一个cover 目标的区间之后，

是先移动右端，然后再移动左端，因为是求和嘛，所以区间里的数字都带上了不是。

可是这里必须先移动左端，因为很有可能开始的一个或者几个字母，是可以shrink掉的，

不然就可能错过正确的结果了。

 

终于搞定了，先找到第一个区间，然后shrink到最小，再右移，再shrink，直到结束。

说到底，还是数组双下标，这个套路的各种演绎值得好好总结一下。

 

讨论区里有人用了deque，或者一个数组本质上还是一样的，找到窗口，压缩，移动。

另外很好奇用hash表怎么速度解决 t 里头有重复字母的情况，例如 “aba”？

（找到一个：这位三哥痛苦不堪地用了三张hash表）

 

class Solution {
public:
    string minWindow(string s, string t) {
        int ls=s.length(), lt=t.length();
        string rst="";
       
        if(!ls || !lt || lt>ls)
            return rst;
           
        if(t==s || (string::npos!=s.find(t)))
            return t;

        //statistics of t
        int st[256]={0};
        for(int tt=lt-1; tt>=0; tt--)
            st[t[tt]]++;

        int start=0, end=0, len=0, count=0;
        int ss[256]={0};
        //get first window
        while(end<ls && count<lt)
        {
            char cc = s[end++];
            if((++ss[cc])<=st[cc])
                count++;
            len++;
        }
       
        //if s doesn't contain all characters in t
        if((end==ls)&&(count<lt))
            return "";
           
        int tmpstart=start, tmpend=end-1, tmplen=len;
        while(tmpend<ls)
        {
            //shrinking for shorter substring
            while(ss[s[tmpstart]] > st[s[tmpstart]])
                ss[s[tmpstart++]]--;
           
            //update length if find a short one.
            tmplen=tmpend-tmpstart+1;
            if(len>tmplen)
                len=tmplen,   start=tmpstart,   end=tmpend;
           
            //extend to next character for next shrinking.
            tmpend++;
            if(tmpend<ls)
                ss[s[tmpend]]++;
        }
        return s.substr(start, len);
    }
};

12 ms.