Longest Substring Without Repeating Characters | LeetCode 3

AFFILIATE LINKS

Great resource I use to learn algorithms.
40% off Tech Interview Pro: http://techinterviewpro.com/terriblewhiteboard
20% off CoderPro: http://coderpro.com/terriblewhiteboard

The way we’ll solve this is using the sliding window technique. For this, we need a set and two pointers. The pointers keep track of the “window”. For example, if the left pointer is at index 1 and the right pointer is at index 3, the window spans indeces 1, 2, and 3.

The way it will work is to loop over each letter in the string. If the set does not already contain that letter, we add it to the set and increment the right pointer by 1. Picture the window expanding to include the next character in the string. If the set already has that letter, we remove it from the set and increase the left pointer by one. Picture the window narrowing from the left to no longer include the leftmost letter.

By using this technique, the window moves further right to include the next letter, but the left pointer makes the window contract from the left until only unique characters are left in the window. Every time the window is about to be increased from the right, the current window length is checked to see if it is longer than the global longest window length. If the new window is longer, the global window length is updated to be the same as the the current window length (since the current window length is the longest window length we’ve seen so far).

This repeats until we have iterated over all characters in the string.

Here is the full implementation.

/**
 * @param {string} s
 * @return {number}
 */
let lengthOfLongestSubstring = function(s) {
    let left = 0;
    let right = 0;
    let set = new Set(); // use a set to keep track of the letters in the current window
    let maxSubstringLength = 0;
    
    while (right < s.length) {
        if (!set.has(s.charAt(right))) {
            set.add(s.charAt(right));
            // check if new window is longer than the longest window
            maxSubstringLength = Math.max(maxSubstringLength, set.size);
            right++; // increase window to the right
        } else {
            set.delete(s.charAt(left));
            // contract window from the left (stops contracting when there are only unique characters in the set)
            left++;
        }
    }
    
    return maxSubstringLength;
};