O(n) simple Javascript solution


  • 0
    H

    This is similar to other top solutions but I feel like it's a little easier to follow. Like others, we begin with a start and end pointer and a max of 0 (which handles our base case of an empty string). Our hashMap stores the character as the key and its position in the string as the value.

    In our loop, we following this as our rule:

    1. If the character is not in the hash map, find the max between the current max and the "new" max with this new character:
    max = Math.max(max, end + 1 - start);
    
    1. If the character is in the hashMap and the index is greater than our current start, find the max between the previous max and the substring we are currently working on. Then set the new start point the character AFTER our first repeated character:
    // say the string is aba, start currently points to "a" at index 0, we want to now point to "b" at index 1, so:
    start = hashMap[char] + 1;
    
    max = Math.max(max, end - start);
    
    1. Set the current index as the location for the current character.
    var lengthOfLongestSubstring = function(s) {
        const hashMap = {};
        let start = 0;
        let end = 0;
        let max = 0;
        
        for (let i = 0; i < s.length; i++) {
            const char = s[i];
            end = i;
    
            if (char in hashMap && hashMap[char] >= start) {
                max = Math.max(max, end - start);
                start = hashMap[char] + 1;
            }
            else {
                max = Math.max(max, end + 1 - start);
            }
            
            hashMap[char] = i;
        }
        
        return max;
    };
    

Log in to reply
 

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