JavaScript O(n) Solution (beats 97.71%)


  • 3
    N

    This solution applies the same algorithm seen in many solutions. (Scan the string while keeping track of left and right indices of the current longest substring without repeating characters. If the current char is a repeat, move the left index directly to the right of the previous instance and update the max length.)

    Instead of using a hash, however, this solution uses the String.prototype.lastIndexOf() function. I found it to be much faster than checking for the existence of a field in a hash object and updating it.

    var lengthOfLongestSubstring = function(s) {
        var maxLen,
            l,
            r;
            
        if (s.length < 2) {
            return s.length;
        }
        
        maxLen = 0;
        
        for (l = 0, r = 1; r < s.length; r++) {
            i = s.lastIndexOf(s[r], r-1);
            if (i >= 0) {
                maxLen = Math.max(maxLen, r - l);
                l = Math.max(l, i + 1);
            }
        }
        return Math.max(maxLen, r - l);
    };

Log in to reply
 

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