Longest Substring Without Repeating Characters

PracticeNeetCode ↗LeetCode ↗

Given a string s, find the length of the longest substring that doesn't contain any repeated characters.

Example

Key Pointers

• This is a variable-size sliding window: expand the right edge, shrink the left edge only when a repeat forces it.
• A hashmap of character → last-seen index lets the left pointer jump straight past the repeat, instead of stepping forward one character at a time.
• Only shrink the window if the repeated character's last occurrence is inside the current window — a stale (already-passed) occurrence shouldn't move the left pointer backward.

Step-by-Step Analysis

1. Initialize left = 0, a hashmap last_seen, and max_len = 0.
2. For each index right, character ch: if ch was seen at or after left, move left to just past that occurrence.
3. Record ch's current index in last_seen.
4. Update max_len with the current window size, right - left + 1.
5. Return max_len.

Complexity

Time: O(n) — Space: O(min(n, charset size))

Code

def lengthOfLongestSubstring(s: str) -> int:
    last_seen = {}
    left = 0
    max_len = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1
        last_seen[ch] = right
        max_len = max(max_len, right - left + 1)
    return max_len

Code Explanation

How the solution above works, piece by piece.

1. last_seen maps each character to the last index where it appeared.
2. right grows the window one character at a time.
3. If ch was seen inside the current window (last_seen[ch] >= left), jump left just past that earlier copy. The >= left check ignores stale entries from before the window.
4. Record ch's new position and update max_len with the window length right - left + 1.
5. left only moves forward, and jumps instead of stepping: O(n) time, O(alphabet) space.

Visual Walkthrough

Running it on s = "abcabcbb":

Video Explanation

NeetCode — Longest Substring Without Repeating Characters, LeetCode 3