Longest Substring Without Repeating Characters — Sliding Window [Google, Amazon, Meta]

Problem Statement

Given a string s, return the length of the longest substring without repeating characters.

Example 1:

Input:  s = "abcabcbb"
Output: 3
Explanation: "abc" is the longest substring without repeating characters.

Example 2:

Input:  s = "pwwkew"
Output: 3
Explanation: "wke" is the answer. Note that "pwke" is a subsequence, not a substring.

Example 3 (edge — all same):

Input:  s = "bbbbb"
Output: 1
Explanation: The window can never grow beyond one character.

Example 4 (edge — single character):

Input:  s = "a"
Output: 1

Constraints:

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols, and spaces.

• Why This Problem Matters
• Building the Sliding Window Intuition
• The HashMap Optimization
• The Critical Bug — Never Move left Backward
• Visual Dry Run — "abcabcbb"
• Common Mistakes
• Solutions
• Approach 1: Set-Based (Clear and Easy to Explain)
• Approach 2: HashMap-Optimized (O(n) — No Inner Loop)
• Complexity Analysis
• Follow-up Questions
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

LeetCode 3 is not just another medium-difficulty problem — it is the entry point to the sliding window technique that appears in dozens of interview problems across Google, Amazon, Meta, Apple, and Microsoft. When recruiters say "know your sliding window," they usually mean: can you solve this problem cleanly and then generalize to harder variants?

The problem shows up regularly at all three interview stages (phone screen, onsite, and virtual onsite) because:

1. It has a brute-force trap. The O(n²) or O(n³) approach is obvious and wrong for large inputs. Interviewers want to see you reason past it.
2. It teaches a transferable template. The expand-right / contract-left pattern directly applies to Minimum Window Substring (LC 76), Longest Repeating Character Replacement (LC 424), Sliding Window Maximum (LC 239), and a dozen more.
3. It has a subtle but devastating bug (the stale hashmap index) that separates candidates who truly understand the pattern from those who memorized it.

The problem is rated Medium, but the insight required — especially the max() guard on the left pointer — is the kind of thing that trips up strong candidates under pressure.

Building the Sliding Window Intuition

Before writing a single line of code, understand what you are maintaining conceptually.

Imagine a sliding window — a contiguous section of the string bounded by two pointers: left (inclusive) and right (inclusive). This window always contains only unique characters.

Here is the mental model:

• Expand: Move right one step to the right, adding s[right] to the window.
• Check: Is the new character already inside the current window [left..right-1]?
  • No duplicate: Great. Update the max window size seen so far.
  • Duplicate found: The window is now invalid. You must shrink it from the left until the duplicate is gone.
• Shrink: Move left rightward until the duplicate is no longer in the window.
• Track max: After every expansion that results in a valid window, record right - left + 1 if it is larger than the current best.

The key insight is that we never move right backward. Once we have explored a position, we never re-examine it. This is what gives us O(n) time — each character is added to the window once and removed at most once.

For the string "abcabcbb":

• We happily expand through a, b, c — window is [a, b, c], length 3.
• We hit a second a. The window is invalid. We shrink from the left: remove a, now window is [b, c].
• We add a again. Window is [b, c, a], still length 3.
• We hit a second b. Shrink: remove b. Window is [c, a]. Add b. Window is [c, a, b], still length 3.
• We hit a second c. Shrink: remove c. Window is [a, b]. Add c. Window is [a, b, c], still length 3.
• We hit a third b. Shrink two steps. Eventually window ends at just [b].
• Answer: 3.

That is the algorithm in plain English. Notice we never said "HashMap" yet.

The HashMap Optimization

The shrink-one-step-at-a-time approach using a Set is clean and correct, but it can be slow in the worst case because we may shrink many steps for one duplicate. We can do better.

Instead of tracking which characters are currently in the window, use a HashMap that stores the most recent index at which each character was seen:

seen[char] = last index where char appeared

When we encounter s[right] and it was previously seen at index i, instead of moving left one step at a time until s[i] leaves the window, we can jump left directly to i + 1. One operation. No inner loop.

The off-by-one detail: We store the index of the character, not the index after it. So the new left is seen[char] + 1, not seen[char]. This is because seen[char] is the position of the duplicate — we want left to be the position immediately after that duplicate, making the window valid again.

This transforms the algorithm from O(n) with a potential hidden constant (each character removed one at a time) to a clean O(n) with no inner loop at all.

The Critical Bug — Never Move left Backward

This is the single most common mistake in interviews and causes solutions to pass most test cases but fail on specific inputs like "abba" or "tmmzuxt".

The bug: You store seen[char] + 1 in left without checking whether that position is already to the left of the current left. If it is, you have just moved left backward, making your window larger and invalid — potentially including characters that are still duplicated.

Concrete example with "abba":

In the buggy version at step 3, seen['a'] is 0, so left becomes 0 + 1 = 1. But left is currently 2! Moving it to 1 means the window now includes s[1]='b' and s[2]='b' — two bs in the window. That is invalid. The buggy solution returns 3 for input "abba", but the correct answer is 2.

The fix is one word: max.

left = max(left, seen[char] + 1)

This single guard ensures left never moves backward. If the stored index is already to the left of the current window, we simply ignore it and keep left where it is. The max() is the entire correctness guarantee of the hashmap approach.

Visual Dry Run — "abcabcbb"

Tracing through the string step by step with left, right, window contents, and running max:

Notice step 7: seen['b'] at that point is index 4 (updated in step 5). So left jumps to 5. The window is s[5..6] = "cb", length 2. The max stays at 3.

At every step, we update seen[char] = right after computing the new left. This is important — we always store the most recent index.

Final answer: 3.

Common Mistakes

1. Moving left backward (forgetting max) The most common interview-killer. Always use left = max(left, seen[char] + 1). Without max, strings like "abba" and "tmmzuxt" will produce wrong answers.

2. Updating seen[char] before adjusting left If you write seen[char] = right before checking for duplicates in the same iteration, you will compare right against right and always find a "duplicate" even when the character is appearing for the first time.

3. Forgetting to handle the empty string When s = "", the loop body never executes and max starts at 0. Most implementations handle this naturally, but make sure you initialize best = 0, not best = 1.

4. Confusing substring with subsequence The problem asks for a contiguous substring, not a subsequence. "pwke" is not a valid answer for "pwwkew". Make sure your window always represents a contiguous section of the string — that is exactly what [left..right] guarantees.

Solutions

Approach 1: Set-Based (Clear and Easy to Explain)

This is the "pure" sliding window. Use a set to track characters in the current window. When a duplicate is found, shrink from the left one step at a time until the duplicate is removed.

Python:

def lengthOfLongestSubstring(s: str) -> int:
    window = set()      # characters currently in the window
    left = 0
    best = 0

    for right in range(len(s)):
        # Shrink from the left until s[right] is no longer in the window
        while s[right] in window:
            window.remove(s[left])
            left += 1

        # s[right] is now safe to add
        window.add(s[right])
        best = max(best, right - left + 1)

    return best

JavaScript:

function lengthOfLongestSubstring(s) {
    const window = new Set();  // characters currently in the window
    let left = 0, best = 0;

    for (let right = 0; right < s.length; right++) {
        // Shrink from the left until s[right] is no longer in the window
        while (window.has(s[right])) {
            window.delete(s[left]);
            left++;
        }

        // s[right] is now safe to add
        window.add(s[right]);
        best = Math.max(best, right - left + 1);
    }

    return best;
}

Approach 2: HashMap-Optimized (O(n) — No Inner Loop)

Use a map to store the last seen index of each character. When a duplicate is found, jump left directly to seen[char] + 1. No inner while loop needed.

Python:

def lengthOfLongestSubstring(s: str) -> int:
    # Maps each character to the index where it was last seen
    seen = {}
    left = 0
    best = 0

    for right, char in enumerate(s):
        if char in seen:
            # The character was seen before.
            # Jump left past its last occurrence — but NEVER move left backward.
            # Without max(), "abba" would give wrong answer 3 instead of 2.
            left = max(left, seen[char] + 1)

        # Always update to the most recent index
        seen[char] = right

        # Window is s[left..right], length = right - left + 1
        best = max(best, right - left + 1)

    return best

JavaScript:

function lengthOfLongestSubstring(s) {
    // Maps each character to the index where it was last seen
    const seen = new Map();
    let left = 0, best = 0;

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

        if (seen.has(char)) {
            // Jump left past the last occurrence — but NEVER move left backward.
            // max() is the critical guard that prevents left from regressing.
            left = Math.max(left, seen.get(char) + 1);
        }

        // Always update to the most recent index
        seen.set(char, right);

        // Window is s[left..right], length = right - left + 1
        best = Math.max(best, right - left + 1);
    }

    return best;
}

Complexity Analysis

Both approaches are O(n) time, but the HashMap version has a smaller constant factor — it does at most n iterations total with no inner loop, whereas the Set version does at most 2n operations (n adds, n removes).

Space: In the worst case (all unique characters) the set or map holds the entire string. In practice it is bounded by m — the size of the character set (26 for lowercase letters, 128 for ASCII, 65536 for Unicode).

Follow-up Questions

These are the questions interviewers ask after you solve LC 3. Having clean answers to these separates good candidates from great ones.

LC 159 — Longest Substring with At Most 2 Distinct Characters Same sliding window template. The window stays valid as long as it contains at most 2 distinct characters. Use a HashMap of character frequencies. When the map has more than 2 keys, shrink from the left, decrementing the frequency of s[left], and remove the key when frequency reaches 0.

LC 340 — Longest Substring with At Most K Distinct Characters Generalizes LC 159 by replacing the constant 2 with a parameter k. The code is nearly identical — just change the condition from len(freq) > 2 to len(freq) > k. This generalization is the pattern that interviewers want you to internalize.

"What if we need the actual substring, not just the length?" Track the starting index of the best window: when you update best, also save best_left = left. At the end, return s[best_left : best_left + best]. This adds O(1) extra tracking with no change in complexity.

"What about Unicode or multi-byte characters?" In Python 3, strings are Unicode by default and character indexing works correctly. In JavaScript, be aware of surrogate pairs for emoji — s[i] can split a multi-byte character. For a robust solution on arbitrary Unicode, use Array.from(s) to get proper code points before processing.

This Pattern Solves

Once you internalize the expand-right / contract-left template from this problem, you can solve:

• LC 76 — Minimum Window Substring: Same two-pointer motion, different validity condition (must contain all chars of t).
• LC 424 — Longest Repeating Character Replacement: Window stays valid if (window size − most frequent char count) ≤ k.
• LC 567 — Permutation in String: Fixed-size window, check if window is an anagram.
• LC 239 — Sliding Window Maximum: Fixed-size window, track max using a monotonic deque.
• LC 438 — Find All Anagrams in a String: Fixed-size sliding window with frequency comparison.

The mental model is always the same: define what makes a window valid, expand right, fix validity from the left, track your answer.

Key Takeaway

The sliding window on LC 3 teaches you the most important two-pointer insight in DSA: a window is valid when it satisfies a constraint, and you expand aggressively until the constraint breaks, then repair from the left. The max(left, seen[char] + 1) guard is not a minor detail — it is the correctness guarantee of the entire hashmap optimization, preventing the left pointer from ever moving backward into territory the window has already abandoned. Master this problem and you have a mental template that directly unlocks a dozen harder problems.