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.

class Solution:
    def lengthOfLongestSubstring(self, 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

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

class Solution:
    def lengthOfLongestSubstring(self, 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

The insight: when s[right] repeats, we know 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.

class Solution:
    def lengthOfLongestSubstring(self, 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 with a strictly single pass (no inner loop); O(min(n, σ)) space. Same asymptotics as Approach 2 — this one just has a smaller constant 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. The upgrade from set-eviction to a last-index map shows a recurring refinement — if the summary structure can tell you where the violation is, the left pointer can jump instead of crawl, though total work is O(n) either way.