Longest Substring

Concept

LeetCode #3.
Problem: Given a string s, find the length of the longest substring without repeating characters.

Input: s = "abcabcbb"
Output: 3 (The answer is "abc", with the length of 3).

Input: s = "pwwkew"
Output: 3 (The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a contiguous substring).

The Sliding Window Strategy

Anytime a problem asks for the “Longest Contiguous Substring/Subarray”, your brain should instantly lock onto the Sliding Window technique.

We use two pointers: left and right. They start at index 0.
We use a Hash Set (Set<string>) to track the characters currently sitting inside our window.

1. The right pointer steps forward one character at a time.
2. We ask the Set: “Is this character already inside the window?”
3. If NO: Add the character to the Set! Calculate the current window size (right - left + 1). Keep a running Math.max of the largest size we’ve seen.
4. If YES: We hit a duplicate! We must shrink the window from the left. We enter a while loop, removing the left character from the Set, and moving left forward, until the duplicate is physically evicted from the window!

Implementation (Using a Set)

// Time Complexity: O(N) (Both left and right pointers only move forward)
// Space Complexity: O(1) (Technically O(K) where K is the charset size. Max 26 for English letters).

function lengthOfLongestSubstring(s: string): number {
    const windowSet = new Set<string>();
    let left = 0;
    let maxLength = 0;

    for (let right = 0; right < s.length; right++) {
        const char = s[right];

        // Did we find a duplicate?
        // Keep shrinking the window from the left until the duplicate is GONE!
        while (windowSet.has(char)) {
            const leftChar = s[left];
            windowSet.delete(leftChar);
            left++;
        }

        // The window is now guaranteed to be free of duplicates.
        // Add the new character!
        windowSet.add(char);

        // Update our max score!
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

The Hash Map Optimization

The Set implementation is flawless and will score 100% in an interview.
However, there is a micro-optimization using a Hash Map instead of a Set.

In the Set approach, if our string is "abcdefghijA", when the right pointer hits the final "A", the left pointer has to slowly while loop 10 times, deleting "a", "b", "c"... until it finally passes the original "a".

If we use a Hash Map, we can store the Exact Index where we last saw each character!
When we hit the final "A", we just ask the Hash Map: “Where was the last ‘A’?” The Map says: “Index 0”.
We can instantly teleport the left pointer to Index 0 + 1! No while loop required!

function lengthOfLongestSubstringOptimized(s: string): number {
    // Map tracks: { Character : Last Seen Index }
    const charIndexMap = new Map<string, number>();
    let left = 0;
    let maxLength = 0;

    for (let right = 0; right < s.length; right++) {
        const char = s[right];

        // Did we see this character before?
        // AND is its last seen index currently inside our active window?
        if (charIndexMap.has(char) && charIndexMap.get(char)! >= left) {
            // Teleport the left pointer directly past the old duplicate!
            left = charIndexMap.get(char)! + 1;
        }

        // Save/Update the exact index of the current character
        charIndexMap.set(char, right);

        // Update our max score
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

Interview Questions

Q: In the Hash Map approach, why is the condition charIndexMap.get(char)! >= left strictly required?
A: This is a famous trap! Imagine the string "abba".

• right = 0 (‘a’): Map sets {a: 0}.
• right = 1 (‘b’): Map sets {b: 1}.
• right = 2 (‘b’): Duplicate ‘b’! Teleport left to Index 1 + 1 = 2. Map sets {b: 2}.
• right = 3 (‘a’): The Map sees ‘a’! The Map says the last ‘a’ was at Index 0.
  If we blindly teleported left to Index 0 + 1 = 1, the left pointer would move BACKWARDS! The old ‘a’ at Index 0 was already physically left behind outside our current window. The >= left check ensures we completely ignore “ghost” duplicates that are already dead and outside our active boundary.