The problem in question

This one to me screams Sliding Window, as we need to identify the longest substring that doesn't repeat.

Brute force approach

I'm having trouble even wrapping my head around the brute force approach. I guess it would be to identify all possible substrings, filter out the ones with repeating chars and then identify the longest remaining string? I chatted with Claude about it, and this is indeed the brute force solution - giving us an O(n^3) runtime - yikes. O(n^2) to generate all the possible substrings, times O(n) to identify if there are duplicates in each of the substrings.

The optimized approach

Using Sliding Window, we can whittle this down to an O(n) runtime solution if we keep track of the largest substring as we go, and when we find duplicates, backtrack to start the new substring at the char immediately after the now-duplicate char. I'd imagine for each substring we'll want a hash of found chars, so that its an O(1) lookup to insert found chars and see if we have duplicates.

With the hash approach, we can store the indices of the found chars, so that when a duplicate is found, we can jump out left pointer that index + 1, and then only care about hash values whose index is greater than our left pointer. I'll then update the index of the found duplicate to the index of the newly found duplicate char.

Originally I thought I'd have to jump back to my left pointer and start iterating every time I moved it, but that's not at all the case. My right pointer is the only thing that's iteratively moving, with my left pointer advancing every time a duplicate is found. At each step I just need to calculate the size of my window - (right pointer - left pointer + 1), and the end, the largest window size is the winner.

Coding the solution

Okay - I'm ready to start coding! I need my hash map to keep track of the found values, a variable to keep track of the index of my left pointer and a variable to keep track of the longest length.

function lengthOfLongestSubstring(s: string): number {
    const chars = s.split("")
    let leftIndex = 0;
    let longest = 0;

    const hashMap: Record<string, number> = {}
    chars.forEach((char, i) => {
        const duplicateIndex = hashMap[char];

        if (duplicateIndex !== undefined && duplicateIndex >= leftIndex) {
            leftIndex = duplicateIndex + 1
        }
        const windowLength = i - leftIndex + 1;
        hashMap[char] = i
        if (longest < windowLength) {
            longest = windowLength
        }
    })
    return longest
};

Even with my solution in mind, this still took a few tries to solve. First, I needed to explicitly check if duplicateIndex is undefined, as sometimes a valid duplicateIndex was 0, which implicitly coalesces to false. I also had a few operations out of order, which led to test strings of empty string returning zero instead of one.

Closing thoughts

This one felt like a magic trick, forreal. To go from O(N^3) to O(N) time complexity is absurd. To put it in perspective - if I had 1000 records, that's a worst case of 1,000,000,000 operations at O(N^3) vs 1,000 operations at O(N) - quite literally a million times faster.

Also, the solution was ultimately simpler than I expected it to be. I expected to iterate forward until I found a duplicate and then backtrack, but with the magic of two pointers, I only needed to move forward through the array, pulling my left pointer forward every time I found a dupe. I'm having more fun with this than I expected. Onto day 3!