Real O(N) time without hash etc


  • 1
    M

    class Solution {
    public:
    string minWindow(string s, string t) {
    int tcount[256], tdiff=0;
    memset(tcount, 0, 256*sizeof(int));

        for (char c : t) 
            if (tcount[c]++ == 0) tdiff++;
    
        int a=0, b=-1, minlen=INT_MAX, len=s.length();
        int scount[256], sdiff=0;
        memset(scount, 0, 256*sizeof(int));
        
        string ans;
        while (b < len) {
            while (b+1<len && sdiff<tdiff) {
                b++;
                if ((scount[s[b]]++)+1==tcount[s[b]])
                    sdiff++;
            }
            
            if (sdiff<tdiff)
                break;
                
            while (a<=b && sdiff==tdiff) {
                if (b-a+1 < minlen)
                    minlen=b-a+1, ans=s.substr(a, minlen);
                
                if ((scount[s[a]]--) == tcount[s[a]] && tcount[s[a]]>0)
                    sdiff--;
                a++;
            }
        }
        
        return ans;
    }
    

    };


  • 0
    T

    There are two hash map implementaitions inlined in your code: scount + sdiff and tcount + tdiff. The hash function is h(c) = c and you have 256 buckets. Remember that map<int, T> is just a generalized sparse version of T[].


Log in to reply
 

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