C++, O(n), one-pass, 16ms


  • 0
    X

    Build up an ideal hash for the previous occurrences of all unique chars. Once a duplicate is found, recalculate maxLen, reset the previous occurrences of all the chars up to and including the previous occurrence of the current char, and then continue. Do not forget to recalculate maxLen once the end of the string is reached.

    int lengthOfLongestSubstring(string s) {
        if(s.empty())
        {
            return 0;
        }
        
        int maxLen = 0;
        int start = 0;
        vector<int> registry;
        registry.resize(256, -1); // char can be the index here
        int j = start;
        while(j < s.length())
        {
            if(registry[s[j]] != -1)
            {
                maxLen = max(maxLen, j - start);
                // clean up the registry up to the previous occurence of the current char, inclusively
                for(int k = start; k < registry[s[j]]; ++k)
                {
                    registry[s[k]] = -1;
                }
                start = registry[s[j]] + 1;                
            }
            registry[s[j]] = j;
            ++j;
        }
        return max(maxLen, j - start);
    }

Log in to reply
 

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