Longest Substring Without Repeating Characters: 5 Key Moves

You've seen this problem in prep lists everywhere. There's a reason for that — it filters candidates fast. You'll solve it in minutes once the pattern clicks.

The trap is starting with nested loops. They feel natural: check every substring, track the longest. That runs in O(n^2) at best and times out on LeetCode's longer cases. Interviewers watch for that opening move. Picking brute force first burns the clock and the impression.

The fix is a sliding window with a hash map. Two pointers mark the current repeat-free stretch. The map remembers each character's last index. When a duplicate lands inside the window, the left edge jumps past it. Each character is visited twice at most. That's O(n) time with one clean pass.

The Rule: Every Character Inside the Window Must Be Unique

Given a string s, return the length of the longest substring without repeating characters. A substring is contiguous: 'abc' from 'abcabcbb' counts, scattered letters don't. The answer for 'abcabcbb' is 3 ('abc'), for 'bbbbb' is 1 ('b'), and for 'pwwkew' is 3 ('wke'). Note the last case — the answer is 'wke', not 'pwke', because the second 'w' kills the longer stretch.

Constraints shape the solution. s holds up to 50,000 characters, so O(n^2) needs ~2.5 billion operations and dies. The alphabet may be ASCII (128 symbols) or full Unicode — either way a hash map fits easily. Return a length, not the substring, though tracking the best start index gives you the text for free.

Walk 'pwwkew' once. Window [0,0]='p', length 1. Extend to [0,1]='pw', length 2. Next 'w' duplicates: jump left past index 1, window [2,2]='w'. Grow to [2,4]='wke', length 3. Final 'w' duplicates index 2, which is inside, so left jumps to 3: window [3,5]='kew', length 3. Max stays 3. One pass, no rescans.

Why Checking Every Substring Reaches 10^9 Operations

The naive plan: enumerate every start i, expand end j while characters stay unique, record the best length. Each expansion builds or checks a set, costing O(n) per pair. Total time is O(n^3) with a naive slice-and-set, or O(n^2) with a careful incremental set. Space is O(min(n, alphabet)) for the set.

Run the numbers. At n = 50,000, O(n^2) means ~1.25 billion inner steps — several seconds past LeetCode's limit, and O(n^3) never finishes. Even n = 5,000 breaks the quadratic version. Brute force is a correctness baseline, not a submission.

Its only value is interview staging: state it in one sentence, name its cost, and move on. 'Brute force checks all O(n^2) substrings at O(n) each — too slow, so I'll use a sliding window.' That sentence earns trust; the code that follows earns the hire.

Sliding Window: Move Left Only When a Duplicate Appears

Maintain a window [left, right] that never holds duplicates, plus a map from character to its last index. For each right from 0 to n-1: if s[right] was seen at index >= left, set left = that index + 1. Then record last[s[right]] = right and update best = max(best, right - left + 1). The max() guard matters — without it, a stale duplicate left of the window yanks left backward and corrupts the invariant.

Proof sketch: invariant holds by construction, since left always jumps past any in-window duplicate. For each right, [left, right] is the longest valid substring ending at right — any earlier start would include the duplicate at last[s[right]]. The global answer must end somewhere, so taking the max over all right values captures it. Each index enters and leaves the window once: 2n pointer moves, O(1) dict work each, hence O(n) time and O(min(n, alphabet)) space.

Compare with the set-only window: it shrinks left one step per duplicate, doing extra iterations the map version skips. Same complexity class, more constant work, longer code. The map is strictly better here.

The Sliding-Window Solution in Full Python

The code above is the complete submission. It runs on LeetCode as-is: class Solution with lengthOfLongestSubstring. Test it mentally on 'abba': right=0 'a', window [0,0], best 1. right=1 'b', window [0,1], best 2. right=2 'b' seen at 1 >= left 0, left becomes 2, window [2,2]. right=3 'a' seen at 0, but 0 < left 2, so left stays; window [2,3]='ba', best stays 2. Correct.

Complexity: O(n) time, O(min(n, alphabet)) space. On ASCII input the dict never exceeds 128 entries — effectively constant memory. No imports, no helpers, no recursion.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last = {}          # char -> most recent index
        left = 0
        best = 0
        for right, ch in enumerate(s):
            if ch in last and last[ch] >= left:
                left = last[ch] + 1
            last[ch] = right
            width = right - left + 1
            if width > best:
                best = width
        return best

Empty Strings, All-Identical Characters and Unicode Input

Empty string returns 0 — the loop never runs and best stays 0. Single character returns 1. All-identical input ('bbbbb') keeps the window at width 1 the whole way. All-unique input ('abcdef') never moves left and returns n. Unicode and spaces behave like any other characters since dict keys are generic.

The sneakiest case is a duplicate of a character that already left the window: 'abba'. The second 'b' (index 2) correctly jumps left to 2; the final 'a' (last seen at 0, now left of left) must not move anything. Code that omits the >= left check fails exactly here. A second trap: very long inputs where candidates slice s[left:right+1] for membership — that hidden O(n) scan turns the 'O(n)' solution quadratic.

Why One Pass Beats the O(n^3) Substring Scan

Time is O(n): right advances n times, left advances at most n times total, dict operations are O(1) average. Space is O(min(n, alphabet)): the map holds one entry per distinct character in the worst case. For ASCII that's capped at 128 — O(1) in practice.

Recap for the whiteboard: one left-to-right pass, no nested loops, no rescans. If an interviewer asks 'can you do better than O(n)?' the answer is no — every character must be examined at least once, so O(n) is optimal. Memory can't drop below the distinct-character set either, since repeats must be remembered.