O(N) algorithm in C++


  • 0
    W

    The logic is, traverse the string, once you meet a new char, find it in hash table
    It means it's a repeated one if you can find one, recalculate the length of new substring. It may be the current length+1 or have to be recalculate. Take the minimum of two.

    If you cannot find it in hash table, then it simply means that it's not a repeated one. So just add one to current length

    int lengthOfLongestSubstring(string s) {
            
            size_t max_count = 0, new_count = 0;
            unordered_map<char,size_t> myMap;
            
            for (size_t i = 0 ; i < s.size(); i++) {
                auto it = myMap.find(s[i]);
                if ( it == myMap.end()) {// cannot find, put in hashtable and increase substr length
                    new_count ++;
                    if( new_count > max_count)
                        max_count = new_count;
                }
                else { // can find, find the start, recalculate the truncated substr length
                    new_count = min( i-myMap[s[i]], new_count +1);
                    max_count = max(max_count, new_count);
                }
                myMap[s[i]] = i;
                
            }
            return max_count;
        }

Log in to reply
 

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