Longest Substring Without Repeating Characters: The Sliding Window Blueprint
The O(n) sliding window solution to Longest Substring Without Repeating Characters — hash set intuition, JavaScript code, a full walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Longest Substring Without Repeating Characters is LeetCode #3, and it is the problem where most people meet the sliding window for the first time. That makes it worth over-learning: the exact mechanics you build here — expand a right edge, shrink a left edge, maintain an invariant in between — reappear in dozens of medium and hard problems, usually with nothing changed but the invariant.
The problem also has a satisfying difficulty curve. The brute force is easy to write and obviously wasteful. The optimal solution is only a few lines longer, yet it drops the running time from quadratic to linear by making one promise: no character is ever examined more than twice.
The problem
Given a string s, return the length of the longest substring that contains no repeating characters. A substring is contiguous — you cannot skip characters.
Input: s = "abcabcbb"
Output: 3 // "abc" is the longest run with no repeats
Input: s = "pwwkew"
Output: 3 // "wke" — note "pwke" doesn't count, it's a subsequenceTwo details in the statement do real work:
- You return the length, not the substring itself — so you only need to track a running best, not reconstruct anything.
- Contiguity is non-negotiable. The
"pwwkew"example exists specifically to punish anyone who quietly solves the subsequence version instead.
The brute force baseline
The straightforward approach: try every starting index, and from each one, extend rightward until a character repeats.
function lengthOfLongestSubstring(s) {
let maxLen = 0;
for (let start = 0; start < s.length; start++) {
const seen = new Set();
for (let end = start; end < s.length; end++) {
if (seen.has(s[end])) break;
seen.add(s[end]);
maxLen = Math.max(maxLen, end - start + 1);
}
}
return maxLen;
}This is O(n²), and the waste is easy to name: it throws away almost everything it learns. Suppose the scan starting at index 0 runs cleanly until it hits a duplicate at index 50. The next iteration restarts at index 1 — and re-verifies characters 1 through 49, all of which it already knows are duplicate-free. On a 50,000-character input, that's over a billion character checks to answer questions the algorithm had already answered.
The key insight: slide the window, never restart it
Reframe the problem as maintaining an invariant: keep one window [left..right] that never contains a duplicate. Then:
- Expand: move
rightforward one character at a time. This is the only way the window grows. - Shrink: if the incoming character
s[right]already lives in the window, evict characters from the left — one by one — until the old copy is gone. Then the new character can enter.
Why is it safe to never move left backward? Because any valid substring that starts before the current left and reaches the current right would have to contain the duplicate that forced the shrink in the first place. Positions behind left are provably dead — the window skips them without checking.
A hash set makes the invariant cheap to enforce: charSet.has(s[right]) answers "would this character break the window?" in O(1), and the set always mirrors exactly the characters inside [left..right].
The payoff is amortized linear time. Each character is added to the set once (when right passes it) and removed at most once (when left passes it). Two touches per character, total — regardless of how the shrinks are distributed.
The optimal solution
This is the exact algorithm the YeetCode visualizer traces, line for line:
function lengthOfLongestSubstring(s) {
const charSet = new Set();
let left = 0;
let maxLen = 0;
for (let right = 0; right < s.length; right++) {
while (charSet.has(s[right])) {
charSet.delete(s[left]);
left++;
}
charSet.add(s[right]);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}Three lines carry all the weight:
while, notif. One eviction may not be enough. If the duplicate sits deep inside the window, every character to its left must go first — the window is contiguous, so eviction proceeds strictly left to right.charSet.delete(s[left]), nevers[right]. You evict the old occupants to make room for the new character; the new character hasn't been added yet.right - left + 1is the window length. Both edges are inclusive, so the+ 1is not optional — dropping it silently undercounts every window by one.
Walkthrough: s = "pwwkew"
You can step through this exact trace interactively and watch the window brackets slide. Here is the full run:
| right | s[right] | In set? | Action | Window after | Set after | maxLen |
|---|---|---|---|---|---|---|
| 0 | p | no | add 'p' | "p" [0..0] | {p} | 1 |
| 1 | w | no | add 'w' | "pw" [0..1] | {p, w} | 2 |
| 2 | w | yes | evict 'p' (left→1), evict 'w' (left→2), add 'w' | "w" [2..2] | {w} | 2 |
| 3 | k | no | add 'k' | "wk" [2..3] | {w, k} | 2 |
| 4 | e | no | add 'e' | "wke" [2..4] | {w, k, e} | 3 |
| 5 | w | yes | evict 'w' (left→3), add 'w' | "kew" [3..5] | {k, e, w} | 3 |
The row to study is right = 2. The duplicate is 'w', but the first character evicted is 'p' — which never repeated at all. That's the contiguity rule at work: left can only advance through characters in order, so 'p' is collateral damage on the way to clearing the 'w' at index 1. The while loop runs twice before the window is valid again.
Also note right = 5: the window "kew" ties the best length of 3 but doesn't beat it, so maxLen stays put. The answer is 3, even though the winning window was found back at step 4.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Check every substring | O(n³) | O(n) | ~n²/2 substrings, each scanned for uniqueness |
| Fresh set per start | O(n²) | O(min(n, σ)) | restarts and re-scans for every start index |
| Sliding window + set | O(n) | O(min(n, σ)) | each char enters once, leaves at most once |
The nested while loop makes the optimal version look quadratic, but the accounting is global, not per-iteration: across the entire run, left only ever moves forward, so the total number of deletions is capped at n. That's amortized analysis in one sentence — bound the total work, not the worst single step.
Space is O(min(n, σ)) where σ is the alphabet size. The set holds one window's worth of distinct characters, and it can never exceed the number of possible distinct characters — 128 for ASCII, 26 for lowercase letters. For fixed alphabets it's effectively O(1).
Common mistakes
- Using
ifinstead ofwhileto shrink. A single eviction only works when the duplicate is atleft. For"abcb", hitting the second'b'requires evicting'a'and the first'b'— anifleaves the duplicate inside and the invariant broken. - Resetting the window to
left = righton a duplicate. This over-corrects and discards valid characters. In"pwwkew"at the final'w', jumpingleftto 5 would shrink the window to just"w"when"kew"was still available. - Computing length as
right - left. Off by one on every single window. Both pointers are inclusive:right - left + 1. - Solving for subsequences. If your answer for
"pwwkew"is 4, you found"pwke"by skipping a character. Substrings are contiguous — the sliding window enforces this automatically, but ad-hoc solutions often don't. - Forgetting the empty string.
s = ""never enters the loop and correctly returns 0 — but only ifmaxLenwas initialized to 0, not to 1.
Where this pattern shows up next
The expand/shrink discipline you built here is one of the most transferable moves in interview prep:
- Two Sum — the other foundational hash-structure pattern: replace an inner loop with an O(1) "have I seen it?" lookup.
- Two Sum II - Input Array Is Sorted — the same two-pointer machinery, but the pointers converge instead of sliding together.
- Is Subsequence — two pointers marching through two strings, and a clean look at how subsequences differ from the substrings in this problem.
- Find the Index of the First Occurrence in a String — a fixed-width window sliding across text, the rigid cousin of the elastic window here.
Before moving on, run the visualizer on "abcdeafghij" — watching the window slide past a late duplicate makes the amortized argument click in a way static text can't.
FAQ
Why is the sliding window solution O(n) when it has a nested while loop?
Because the inner loop's total work is bounded globally, not per iteration. The left pointer only ever moves forward, and each forward step deletes exactly one character from the set — so across the entire run there are at most n deletions, no matter how they're distributed. Combined with the n additions from the outer loop, every character is touched at most twice, giving O(2n) = O(n). This is amortized analysis: an individual step can be expensive as long as the total is capped.
What is the space complexity of Longest Substring Without Repeating Characters?
O(min(n, σ)), where σ is the size of the character alphabet. The hash set only ever holds the characters inside the current window, and it can't contain more distinct characters than the alphabet allows — 128 for ASCII or 26 for lowercase English letters. For inputs drawn from a fixed alphabet, the set size is bounded by a constant, making space effectively O(1).
Can I use a hash map instead of a set to shrink faster?
Yes. Storing each character's last-seen index in a map (char → index) lets left jump directly past the old duplicate instead of evicting one character at a time: when s[right] was last seen at index j and j >= left, set left = j + 1. The j >= left guard matters — without it, a stale entry from before the current window can drag left backward and corrupt the invariant. Both versions are O(n); the set version does more pointer steps but is easier to reason about, which is why it's the one to learn first.
Why can't I just restart the window when I hit a duplicate?
Restarting — setting left = right — throws away characters that are still valid. When the second 'w' in "pwwkew" arrives at index 5, only the older 'w' at index 2 conflicts; 'k' and 'e' are innocent and belong in the next window. Shrinking just far enough to clear the duplicate preserves them, and the window "kew" of length 3 survives. A full reset would report a shorter answer on inputs where the best window straddles a duplicate.
Does "substring" mean the characters have to be contiguous?
Yes — that's the defining difference between a substring and a subsequence. A substring is an unbroken run of consecutive characters; a subsequence may skip characters while preserving order. For "pwwkew", the answer is 3 ("wke"), not 4 ("pwke"), because "pwke" skips a 'w'. The sliding window enforces contiguity by construction: the window is always the literal range [left..right] of the string.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.