ASAPUtils
The signal
“Longest … such that no repeats” — longest, contiguous, with a constraint you can test incrementally. That’s the variable sliding window signal verbatim, and this is the problem to learn the template on.
Approach ladder
1. Brute force — O(n³) or O(n²)
Check every substring for uniqueness. Even the optimised version that extends until a repeat is O(n²).
2. What is it wasting?
When the substring starting at i fails at position j, the brute force restarts from i+1 and
re-examines everything between. But it already knows those characters were distinct — that work
doesn’t need repeating.
3. The insight
Keep a window [l, r] that is always valid (no repeats inside it). Push r forward every
step. When the incoming character is already in the window, pull l forward until it isn’t. The
window never has to be rebuilt from scratch.
4. Optimal — O(n)
int lengthOfLongestSubstring(string s) {
unordered_set<char> win;
int l = 0, best = 0;
for (int r = 0; r < (int)s.size(); r++) {
while (win.count(s[r])) { win.erase(s[l]); l++; }
win.insert(s[r]);
best = max(best, r - l + 1);
}
return best;
}
function lengthOfLongestSubstring(s) {
const win = new Set();
let l = 0, best = 0;
for (let r = 0; r < s.length; r++) {
while (win.has(s[r])) { win.delete(s[l]); l++; }
win.add(s[r]);
best = Math.max(best, r - l + 1);
}
return best;
}
5. The jump variant
Instead of shrinking one character at a time, store each character’s last index and jump l
directly:
function lengthOfLongestSubstring(s) {
const last = new Map();
let l = 0, best = 0;
for (let r = 0; r < s.length; r++) {
if (last.has(s[r])) l = Math.max(l, last.get(s[r]) + 1); // max() is essential
last.set(s[r], r);
best = Math.max(best, r - l + 1);
}
return best;
}
Math.max(l, …) is doing real work: a stale index from before the current window would otherwise
drag l backwards. Dropping it is the classic bug in this variant.
Walkthrough
"abcabcbb":
| r | char | window before | action | best |
|---|---|---|---|---|
| 0 | a | "" | add → "a" | 1 |
| 1 | b | "a" | add → "ab" | 2 |
| 2 | c | "ab" | add → "abc" | 3 |
| 3 | a | "abc" | repeat: drop a, add → "bca" | 3 |
| 4 | b | "bca" | repeat: drop b, add → "cab" | 3 |
Complexity
- Time O(n) — each pointer moves at most n times.
- Space O(min(n, k)) — the window holds at most one of each distinct character.
Traps
ifinstead ofwhilein the shrink step. One removal may not be enough.- Forgetting
Math.maxin the jump variant. Window moves backwards, answer inflates. - Recording
bestbefore addings[r]. Off by one. - Assuming lowercase. The problem allows letters, digits, symbols and spaces — a 26-slot array is wrong here; use a set or map.
Blank re-solve prompt
Return the length of the longest substring with no repeated characters, in O(n). Then write the jump variant and explain why the max is needed.