LeetCode 3 ·
Medium
Longest Substring Without Repeating Characters
Find the length of the longest substring with all distinct characters.
Try it
Step through the core mechanic. The simulator below runs the sliding window shape this problem is built on.
Interactive · Sliding-window walkthrough LC 3: longest substring without repeating characters
0
a
1
b
2
c
3
a
4
b
5
c
6
b
7
b
start: window is empty
window0 set{} best0
Why sliding window works.
The right edge always moves forward. The left edge only moves forward (never
back). Each character enters and leaves the window at most once, so the total
work is O(n) — even though the algorithm looks like a nested loop.
This "amortised linear" pattern is the core insight: a while-inside-a-for is
fine if the inner work is bounded by total movements, not per-iteration.
The approach
Variable window with a set. Expand the right edge each step; when the new character duplicates one inside, advance the left edge until the duplicate leaves. Record the window length after each expand.
| Aspect | Value |
|---|---|
| Pattern | Sliding window |
| Recognise it by | Longest window with no repeats. |
| Time complexity | O(n) |
| Space complexity | O(Σ) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.