Longest Substring Without Repeating Characters (LeetCode 3)
You have a string s. Among all of its contiguous substrings, find the longest one that never repeats a character, and report its length.
Worked Examples
s = "abcabcbb"3s = "bbbbb"1s = "pwwkew"3⚖️Formal Constraints & Bounds
0 <= s.length <= 105sconsists of English letters, digits, symbols and spaces.
Core Insight
Maintaining a hash set of characters currently in the window allows O(1) duplicate checks and amortized O(N) window repairs.
Real-World Scenario & Production Applications
Tokenization parsers, compression algorithms (LZW dictionary windows), and network session deduplication caches.
Subproblems & Recurrence Decomposition3 Phases
Iterate right from 0 to N-1. Maintain a hash map char_map storing the latest index where each character was observed.
char_map = {} # char -> latest seen index
left = 0
max_len = 0Step-by-Step Execution Trace Table
| Step | Action | window | left | max_len |
|---|---|---|---|---|
| 1 | add a (right=0) | a | 0 | 1 |
| 2 | add b (right=1) | ab | 0 | 2 |
| 3 | add c (right=2) | abc | 0 | 3 |
| 4 | right=3 is a — duplicate drop s[0]='a' | bc | 1 | 3 |
| 5 | window legal add a | bca | 1 | 3 |
| 6 | right=4 is b — duplicate drop s[1]='b' | ca | 2 | 3 |
| 7 | window legal add b | cab | 2 | 3 |
| 8 | right=5 is c — duplicate drop s[2]='c' | ab | 3 | 3 |
| 9 | window legal add c | abc | 3 | 3 |
| 10 | right=6 is b — duplicate drop s[3]='a' | bc | 4 | 3 |
| 11 | still duplicate drop s[4]='b' | c | 5 | 3 |
| 12 | window legal add b | cb | 5 | 3 |
| 13 | right=7 is b — duplicate drop s[5]='c' | b | 6 | 3 |
| 14 | still duplicate drop s[6]='b' | (empty) | 7 | 3 |
| 15 | window legal add b | b | 7 | 3 (Search complete) |
| 1 | seen_chars = set() |
| 2 | left = 0 |
| 3 | max_len = 0 |
| 4 | for right in range(len(s)): |
| 5 | while s[right] in seen_chars: |
| 6 | seen_chars.remove(s[left]) |
| 7 | left += 1 |
| 8 | seen_chars.add(s[right]) |
| 9 | max_len = max(max_len, right - left + 1) |
| 10 | return max_len |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
This is the pattern's first growing window — both edges now move independently, and the shrink direction is triggered by a violation instead of a fixed size.
📸 The Analogy: A Photo Frame That Only Shrinks When It Has To
Picture a camera frame sliding across a sentence, always trying to grow as wide as possible while keeping "no repeated letter visible" true. You keep sliding the right edge outward, capturing one more letter each time — as long as that letter isn't already inside the frame. The moment it would create a duplicate, you don't restart from scratch; you just nudge the left edge of the frame inward, one letter at a time, only far enough to evict the earlier copy of that duplicate letter. Then you keep growing right again.
🔑 The Key Idea in the Code
The frame never resets to empty and restarts — it only ever shrinks by the minimum amount needed to repair the violation, which is what keeps this an O(N) pass instead of an O(N²) restart-from-scratch scan.
Recording answer inside the duplicate loop: In longest-window problems (LC 3), the window is valid AFTER the duplicate character has been removed. Record
max_len = max(max_len, right - left + 1)after the innerwhileloop, not inside it.Evicting wrong character from set: When duplicate
s[right]is found, you must removes[left]from the set and incrementleft += 1untils[right]is no longer in set, not removes[right]directly.Stale index lookup with character map: If storing
{char: last_seen_index}, jumpingleft = map[char] + 1is only valid ifmap[char] >= left. Forgettingmax(left, map[char] + 1)movesleftbackwards!
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"the longest one that never repeats a character" among contiguous substrings: the longest window that stays valid under a no-repeat rule (Longest Window).
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: after the repair loop, seen_chars is exactly the set of characters in s[left..right], with no repeats.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Measuring too early: update
max_lenonly after thewhileloop; before it, the window may still hold the repeat.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use a Longest Window. I move right one character at a time and keep seen_chars equal to the characters between left and right. If s[right] is already in seen_chars, the window holds a repeat, so I remove s[left] and move left forward until the old copy is gone. That loses nothing: any window that ends at right and starts before the new left still holds the repeat. Then I add s[right] and record right - left + 1 in max_len. The trap is measuring too early: I update max_len only after the repair loop, because before it the window can still hold a duplicate. On bbbbb, measuring before the repair gives 2 instead of 1. Each character is added once and removed at most once, so it's
O(N)time, with O(min(N, alphabet)) space for the set."
Complexity & Mathematical Proof
O(N)
Look at the loops: for right in range(len(s)): runs N times and adds s[right] to seen_chars once each time. The inner while s[right] in seen_chars: removes s[left] and moves left forward; a character can only be removed after it was added, so across the whole run there are at most N removals. Set membership, add and remove are O(1) on average, so the total is N + N = O(N).
O(min(N, Sigma))
Look at memory allocation: The call stack is iterative O(1). seen_chars holds only distinct characters of the current window, so at most min(N, Sigma) of them (at most 128 for ASCII).
N additions + at most N removals = O(N)
Derivation Progression
N iterations
The outer loop adds each character of s to seen_chars exactly once.
at most N removals in total
left only moves forward, and each move removes one character that was added earlier.
N + N = O(N)
Every character enters and leaves the window at most once.
Variable Definitions
Total length of the string
Character set size (at most 128 ASCII characters)
Memory Architecture & Bounds
O(1) Iterative loop with zero recursion frames
O(min(N, Sigma)) The set seen_chars
O(1) Returns max length integer
Boundary Best / Worst Cases
.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "longest substring without repeating characters". Monotonic sliding window: before right is added, check whether adding it would break the rule; if it would, shrink/jump left to repair first, then add right.
. Time budget strictly , space . On a long stream the set never holds more than the alphabet, so memory stays bounded however long the input is.
An empty string needs no special case: the loop never runs and max_len stays 0. If you jump left with an index map instead of a set, use left = max(left, last_seen[ch] + 1): in "abba" the second 'a' was last seen before left, and a plain jump would move left backwards.
Longest Substring Without Repeating Characters (LeetCode 3)
You have a string s. Among all of its contiguous substrings, find the longest one that never repeats a character, and report its length.
Worked Examples
s = "abcabcbb"3s = "bbbbb"1s = "pwwkew"3⚖️Formal Constraints & Bounds
0 <= s.length <= 105sconsists of English letters, digits, symbols and spaces.
Core Insight
Maintaining a hash set of characters currently in the window allows O(1) duplicate checks and amortized O(N) window repairs.
Real-World Scenario & Production Applications
Tokenization parsers, compression algorithms (LZW dictionary windows), and network session deduplication caches.
Subproblems & Recurrence Decomposition3 Phases
Iterate right from 0 to N-1. Maintain a hash map char_map storing the latest index where each character was observed.
char_map = {} # char -> latest seen index
left = 0
max_len = 0Step-by-Step Execution Trace Table
| Step | Action | window | left | max_len |
|---|---|---|---|---|
| 1 | add a (right=0) | a | 0 | 1 |
| 2 | add b (right=1) | ab | 0 | 2 |
| 3 | add c (right=2) | abc | 0 | 3 |
| 4 | right=3 is a — duplicate drop s[0]='a' | bc | 1 | 3 |
| 5 | window legal add a | bca | 1 | 3 |
| 6 | right=4 is b — duplicate drop s[1]='b' | ca | 2 | 3 |
| 7 | window legal add b | cab | 2 | 3 |
| 8 | right=5 is c — duplicate drop s[2]='c' | ab | 3 | 3 |
| 9 | window legal add c | abc | 3 | 3 |
| 10 | right=6 is b — duplicate drop s[3]='a' | bc | 4 | 3 |
| 11 | still duplicate drop s[4]='b' | c | 5 | 3 |
| 12 | window legal add b | cb | 5 | 3 |
| 13 | right=7 is b — duplicate drop s[5]='c' | b | 6 | 3 |
| 14 | still duplicate drop s[6]='b' | (empty) | 7 | 3 |
| 15 | window legal add b | b | 7 | 3 (Search complete) |
| 1 | seen_chars = set() |
| 2 | left = 0 |
| 3 | max_len = 0 |
| 4 | for right in range(len(s)): |
| 5 | while s[right] in seen_chars: |
| 6 | seen_chars.remove(s[left]) |
| 7 | left += 1 |
| 8 | seen_chars.add(s[right]) |
| 9 | max_len = max(max_len, right - left + 1) |
| 10 | return max_len |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
This is the pattern's first growing window — both edges now move independently, and the shrink direction is triggered by a violation instead of a fixed size.
📸 The Analogy: A Photo Frame That Only Shrinks When It Has To
Picture a camera frame sliding across a sentence, always trying to grow as wide as possible while keeping "no repeated letter visible" true. You keep sliding the right edge outward, capturing one more letter each time — as long as that letter isn't already inside the frame. The moment it would create a duplicate, you don't restart from scratch; you just nudge the left edge of the frame inward, one letter at a time, only far enough to evict the earlier copy of that duplicate letter. Then you keep growing right again.
🔑 The Key Idea in the Code
The frame never resets to empty and restarts — it only ever shrinks by the minimum amount needed to repair the violation, which is what keeps this an O(N) pass instead of an O(N²) restart-from-scratch scan.
Recording answer inside the duplicate loop: In longest-window problems (LC 3), the window is valid AFTER the duplicate character has been removed. Record
max_len = max(max_len, right - left + 1)after the innerwhileloop, not inside it.Evicting wrong character from set: When duplicate
s[right]is found, you must removes[left]from the set and incrementleft += 1untils[right]is no longer in set, not removes[right]directly.Stale index lookup with character map: If storing
{char: last_seen_index}, jumpingleft = map[char] + 1is only valid ifmap[char] >= left. Forgettingmax(left, map[char] + 1)movesleftbackwards!
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"the longest one that never repeats a character" among contiguous substrings: the longest window that stays valid under a no-repeat rule (Longest Window).
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: after the repair loop, seen_chars is exactly the set of characters in s[left..right], with no repeats.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Measuring too early: update
max_lenonly after thewhileloop; before it, the window may still hold the repeat.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use a Longest Window. I move right one character at a time and keep seen_chars equal to the characters between left and right. If s[right] is already in seen_chars, the window holds a repeat, so I remove s[left] and move left forward until the old copy is gone. That loses nothing: any window that ends at right and starts before the new left still holds the repeat. Then I add s[right] and record right - left + 1 in max_len. The trap is measuring too early: I update max_len only after the repair loop, because before it the window can still hold a duplicate. On bbbbb, measuring before the repair gives 2 instead of 1. Each character is added once and removed at most once, so it's
O(N)time, with O(min(N, alphabet)) space for the set."
Complexity & Mathematical Proof
O(N)
Look at the loops: for right in range(len(s)): runs N times and adds s[right] to seen_chars once each time. The inner while s[right] in seen_chars: removes s[left] and moves left forward; a character can only be removed after it was added, so across the whole run there are at most N removals. Set membership, add and remove are O(1) on average, so the total is N + N = O(N).
O(min(N, Sigma))
Look at memory allocation: The call stack is iterative O(1). seen_chars holds only distinct characters of the current window, so at most min(N, Sigma) of them (at most 128 for ASCII).
N additions + at most N removals = O(N)
Derivation Progression
N iterations
The outer loop adds each character of s to seen_chars exactly once.
at most N removals in total
left only moves forward, and each move removes one character that was added earlier.
N + N = O(N)
Every character enters and leaves the window at most once.
Variable Definitions
Total length of the string
Character set size (at most 128 ASCII characters)
Memory Architecture & Bounds
O(1) Iterative loop with zero recursion frames
O(min(N, Sigma)) The set seen_chars
O(1) Returns max length integer
Boundary Best / Worst Cases
.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "longest substring without repeating characters". Monotonic sliding window: before right is added, check whether adding it would break the rule; if it would, shrink/jump left to repair first, then add right.
. Time budget strictly , space . On a long stream the set never holds more than the alphabet, so memory stays bounded however long the input is.
An empty string needs no special case: the loop never runs and max_len stays 0. If you jump left with an index map instead of a set, use left = max(left, last_seen[ch] + 1): in "abba" the second 'a' was last seen before left, and a plain jump would move left backwards.