O(n) C++ code - 25ms - Used hashing


  • 0

    My O(n) 25ms C++ code . Used hashing to check duplicates. Please check code for more understanding.

    int lengthOfLongestSubstring(string s) {
            int hash[256];
            int l = s.length();
            if(l == 0 )
                return 0;
            
            int ans = 1;
            for( int i = 0 ;i < 256;i++ ) 
                hash[i] = -1;
                
            hash[ s[0] ] = 0;
            int curL = 1;
            
            for( int i = 1 ;i < l;i++ ) {
                int curChar = s[i];
                int h = hash[curChar];
                //dup
                if( h > -1 ) {
                    
                    //int after = i-1-h;
                    //int before = h-curL+after+1;
                    int before = i-curL;
                    
                    for( int k = before ; k <= h ; k++ ) {
                        hash[s[k]] = -1;
                    }
                    curL = i-h;
                } else {
                    curL++;
                }
                hash[curChar] = i;
                ans = max(ans,curL);
            }
            return ans;
        }    
    

Log in to reply
 

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