My 12ms simple C++ code (O(1) space, O(N) time)


  • 10
    D

    Just used an array dict to count the occurence of the letters in t. To distinguish the letters that are not in t, we initialize dict with -slen and for those letters that are not in t, their corresponding elements in dict will be -slen. For example, t="abc", then dict['a']= dict['b']=dict['c']=1, while the others, such as dict['d'] = -slen. so if dict[x] == -slen, we know x is not in t. Of course, you can use an unordered_map to simplify the logic, but it is much slower.
    After building dict, we scan the string s, we use start to track the starting point of the current window and move i forward: we decrease dict[s[i]], if s[i] is a letter in t and in the current window we don't find all the occurence of s[i] (i.e. (--dict[s[i]]>=0) ), then s[i] will be counted as one letter of t. we decrease count by 1 and if count ==0 (i.e. --count ==0), it means we find all the letters of t in the current window. Then we move start to find the minium window, if s[start] is not in t (dict[s[start]]<= -slen ) or if we have more than enough such letters in the current window (i.e. (++dict[s[start]] <= 0, for example, s= aaab, t= ab, say start = 0, i=3, then in that case dict[s[0]] = -1, so we can move start to 1 (so dict[s[0]] = 0), and stop at 2 (dict[s[0]] = 1)). After while, we find start of the minium window ending at i, then we compare such window with the one we found so far (with length minL and starts at minS). If it is shorter than minL, update minL and minS. At last, we increase start and count, and continue the search.
    Since we have to move i and start through s, the complexity is O(N)

    class Solution {
    public:
        string minWindow(string s, string t) {
            int slen = s.size(), tlen = t.size(), i, start=0, count, minL = INT_MAX, minS;
            int dict[128];
            fill_n(dict,128,-slen);
            for(i=0;i<tlen;++i) dict[t[i]] = dict[t[i]]>0? (dict[t[i]]+1):1;
            
            for(i=0, count = tlen; i<slen;++i)
            {
                if( (--dict[s[i]]>=0) && (--count == 0) )
                {
                    while(dict[s[start]]<=-slen || (++dict[s[start]] <= 0) ) ++start;
                    if(minL>i-start+1)
                    {
                        minL = i-start+1;
                        minS = start; 
                    }
                    count=1;
                    ++start;
                }
            }
            return minL==INT_MAX? "":s.substr(minS, minL);
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.