Variable sliding window
mediumThe longest substring without repeats, in one pass. Neither pointer ever reverses, so together they take at most 2n steps even though the window itself grows and shrinks unpredictably.
O(n)Space O(k) for the alphabetSaved in this browser - no sign-up, nothing sent anywhere.
How variable sliding window works
The window s[left..right] always holds the longest run without a repeated character that ends at right. Each step, right advances one letter. If the new letter already occurs inside the window, left jumps to one past that occurrence - the smallest shrink that restores uniqueness. Grow when possible, shrink only when forced.
The linear bound is an accounting argument: right moves n times, and left only ever moves forward to catch up, so the two pointers make at most 2n moves combined. The window can grow and shrink raggedly - total work stays linear because neither pointer ever revisits an index.
The map from character to last index is what lets left jump instead of crawl. On a duplicate, left = seen[c] + 1 lands in one assignment where shrink-by-one would loop. The guard matters: only a previous occurrence at or after left counts - anything earlier lies outside the window and is no duplicate at all.
Step by step
- Scan "abcabcbb". The letters a, b, c at indices 0..2 are all new - the window grows to "abc", best = 3.
- Index 3 reads a. The map says a last appeared at index 0, inside the window - left jumps to 1. Window "bca", still length 3.
- Index 4 reads b, last seen at 1, at or after left - left jumps to 2. Window "cab".
- Index 5 reads c, last seen at 2 - left jumps to 3, giving "abc" again. best stays 3.
- Index 6 reads b, last seen at 4 - left jumps to 5. The window shrinks to "cb"; best still remembers 3.
- Index 7 reads b again, seen at 6 - left jumps to 7. The scan ends: the answer is 3, from "abc".
Complexity
| Worst case time | O(n) |
|---|---|
| Space | O(k) for the alphabet |
Reference implementation
Python
def longest_unique_substring(s):
"""Longest substring with no repeated character, in one pass."""
seen = {}
left = best = 0
for right, c in enumerate(s):
if c in seen and seen[c] >= left:
left = seen[c] + 1 # shrink past the old occurrence
seen[c] = right
best = max(best, right - left + 1)
return bestJavaScript
function longestUnique(s) {
const seen = new Map();
let left = 0, best = 0;
for (let right = 0; right < s.length; right++) {
const c = s[right];
if (seen.has(c) && seen.get(c) >= left) left = seen.get(c) + 1;
seen.set(c, right);
best = Math.max(best, right - left + 1);
}
return best;
}Worth noticing
Right always advances; left only ever catches up
Neither pointer moves backwards, so together they take at most 2n steps. That is the accounting behind the linear bound - even though the window itself grows and shrinks unpredictably.
The map lets left jump instead of crawl
Storing each character's last index means the window can skip straight past a duplicate in one move. Without it you would shrink one character at a time, still linear amortised but with more work per step.
`seen[c] >= left` is the subtle guard
A character may be in the map from *before* the current window, in which case it is not a duplicate at all. Drop that check and left can jump backwards, silently corrupting the window - the classic bug in this pattern.
Common pitfalls
- Dropping the seen[c] >= left guard. A character remembered from before the current window is not a duplicate, and without the check left can jump backwards and corrupt the window.
- Setting left = seen[c] instead of seen[c] + 1, which keeps the old occurrence inside the window - the duplicate survives and every later length is one too generous.
- Measuring right - left + 1 before the shrink instead of after, which records window lengths that were never actually valid.
- In count-based versions of the pattern (minimum window substring, at most k distinct), forgetting to decrement the leaving character's count as left advances - the window then believes in letters it no longer contains.
Where it is used
- Longest substring without repeating characters - LeetCode 3, and this page's exact code.
- Longest substring with at most k distinct characters: the same shape, with a count map instead of last indices.
- Minimum window substring: grow until every required character is covered, shrink while it stays covered, record the tightest.
- Max consecutive ones with k flips allowed - the uniqueness rule becomes a budget, the movement rules stay identical.
Frequently asked questions
What are the time and space complexity of the variable sliding window?
O(n) time: right advances n times and left, which never moves backwards, at most n more - 2n pointer moves in total. Space is O(k) for the alphabet, since the map keeps one last-seen index per distinct character: 26 entries for lowercase letters, however long the string.
Why is sliding window O(n) and not O(n²)?
Because neither pointer ever retreats. A single duplicate can move left several places at once, but each pointer crosses each index at most once over the whole run. Work is charged to pointer movement, and movement is capped at 2n - not windows times width.
When should the window shrink?
Exactly when it violates its condition, and by the least amount that repairs it. Here that means: when the entering character already appears at or after left, jump left to one past that occurrence. Shrinking early wastes length; shrinking late counts invalid windows.
How do I recognise a variable sliding window problem?
The answer is a contiguous stretch, and validity is monotone: growing the window can only add violations, shrinking can only remove them. Uniqueness works that way; so do budgets and coverage counts. Without that monotone structure, never-look-back pointer movement stops being safe.