Longest Substring Without Repeating Characters

Problem

Given a string s, return the length of the longest contiguous substring in which no character appears more than once.

Substring means consecutive characters — "ace" inside "abcde" doesn’t count (that’s a subsequence). The answer is a length only; you don’t need to return the substring itself.

Examples

• s = "abcabcbb" → 3 — "abc" is the longest stretch with all-distinct characters; the fourth character a repeats.
• s = "bbbbb" → 1 — every window longer than one character contains a repeat.
• s = "pwwkew" → 3 — "wke" (or "kew") works; "pwke" is not contiguous in a duplicate-free way because of the double w.

Constraints

• 0 <= len(s) <= 5 * 10^4
• s consists of English letters, digits, symbols, and spaces (general ASCII — don’t assume 26 letters).

O(n²) window checking is around 2.5 * 10^9 character comparisons in the worst case; the expected solution is a single O(n) pass.

Think about it first

TL;DR

Sliding window with a last-seen-index map — O(n) time, O(min(n, σ)) space (σ = alphabet size).

Approach 1 — Brute force

Check every start index; extend until the first repeat.

def lengthOfLongestSubstring(s: str) -> int:
    best = 0
    for i in range(len(s)):
        seen: set[str] = set()
        j = i
        while j < len(s) and s[j] not in seen:
            seen.add(s[j])
            j += 1
        best = max(best, j - i)
    return best

Complexity: O(n²) time, O(min(n, σ)) space. At n = 5 * 10^4 this is ~10^9+ operations — too slow, and it redoes almost identical scans for adjacent start points.

Approach 2 — Sliding window with a set

“All characters distinct” is a monotone property: shrinking a valid window keeps it valid, and growing an invalid one keeps it invalid. So the smallest valid left for each right only moves forward, and the two pointers each traverse the string once.

def lengthOfLongestSubstring(s: str) -> int:
    window: set[str] = set()
    left = 0
    best = 0
    for right, ch in enumerate(s):
        while ch in window:            # evict until the duplicate of ch is gone
            window.remove(s[left])
            left += 1
        window.add(ch)
        best = max(best, right - left + 1)
    return best

Walkthrough on s = "pwwkew":

Notice step 2: left advances one character at a time until the earlier w leaves.

Complexity: each index enters and leaves the window at most once → O(n) time; O(min(n, σ)) space.

Approach 3 — Jump the left pointer with a last-index map

When s[right] repeats, the map tells us exactly where its previous copy sits. Instead of evicting one character at a time, jump left straight past that copy. The map replaces the inner loop entirely.

def lengthOfLongestSubstring(s: str) -> int:
    last: dict[str, int] = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:   # previous copy is inside the window
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

Walkthrough on s = "abcabcbb" (indices 0–7):

Answer: 3.

Complexity: O(n) time in a single pass (no inner loop); O(min(n, σ)) space. Same asymptotics as Approach 2, with a smaller constant factor and a subtler correctness condition.

Common pitfalls

• Forgetting last[ch] >= left in Approach 3. A stale entry from before the current window must not drag left backward; e.g. "abba" — at the final a, last["a"] = 0 is outside the window (left = 2) and must be ignored, else left regresses to 1 and you overcount.
• Updating best before restoring validity. Evict/jump first, then measure; otherwise you measure a window containing the duplicate.
• Assuming a 26-letter alphabet. The input includes digits, symbols, and spaces — a dict/set is right; a fixed 26-slot array is not.
• Empty string. The loop body never runs and best = 0 is returned — make sure your initialization allows that.

Pattern takeaway

The canonical “longest valid window” template: validity (“no duplicates”) is monotone under shrinking, so grow right every step and move left only forward, only as far as needed. Moving from set-eviction to a last-index map shows a recurring refinement: when the auxiliary structure records where the violation is, the left pointer can jump directly instead of advancing one step at a time. Total work is O(n) either way.