Sliding Window
Grow and shrink the window
Before you start
- Open lesson
Map a value to its index
This window stores each character's last index in a dict, the way Two Sum stored values.
Why it matters
Editors, protocol parsers, and analytics jobs often measure the longest contiguous run that obeys a uniqueness rule. Restarting the scan at every character repeats long prefixes. For "tmmzuxt", return the longest no-repeat length, 5, in O(n) time without restarting from every possible beginning.
Example
Longest Substring Without Repeating Characters
Given a string s, return the length of the longest substring that contains no repeating characters.
- Input
- s = "tmmzuxt"
- Output
- 5
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Longest Substring Without Repeating Characters
s = "tmmzuxt"→5
The baseline, Extend from every start, is O(n²) · O(min(n, m)). The better model below keeps this exact input and removes that bottleneck.
In "tmmzuxt", the second "m" moves the start past the first "m", while the final "t" points to an occurrence already outside the current range. A last-index map updates one live range instead of brute force restarting at every index.
Index the characters of "tmmzuxt" as t₀ m₁ m₂ z₃ u₄ x₅ t₆. When m₂ arrives, its earlier copy is at 1 inside the current range, so set left to 2. The valid range then grows through "mzuxt", length 5.
The final t was last seen at index 0, which is already left of 2. It does not break "mzuxt", so left must not move backward. Recording each character's latest index makes both cases a direct comparison with left.
Visual anchor
Longest Substring Without Repeating Characters
s
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.