C++ solution with std::map


  • 0
    K

    Just one trick here: keep updating the map with new symbols as we slide down the string, but ignore matches that are found before your current substring candidate starts:

        int lengthOfLongestSubstring(string s) {
            map<char,int> dict;
            int subStart  = 0;
            int maxSubLen = 0;
    
            for(int pos=0; pos<s.length(); pos++){
                /* the character repeats and it was encountered in the current substring candidate? */
                if( dict.find( s[pos] ) != dict.end() && dict[ s[pos] ] >= subStart )
                    subStart = dict[ s[pos] ] + 1;
                dict[ s[pos] ] = pos;
                if( pos+1 - subStart > maxSubLen ) maxSubLen = pos+1 - subStart;
            }
    
            return maxSubLen;
        }
    

Log in to reply
 

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