Variable-Size Windows
The longest substring without repeats needs a window that grows and shrinks as the data demands.
The problem
You're writing the logic for a password strength meter, and one rule is: find the longest
run of characters the user typed with no repeated character. Type abcabcbb and the best
clean run is abc, length 3. Type pwwkew and it's wke, length 3. The window you care
about has no fixed size — it's as long as it can be while staying valid.
That "as long as it can be" is the catch. A fixed window of size k doesn't fit, because you
don't know k in advance — it's the answer. You need a window that stretches when things
are going well and contracts the moment a rule is broken.
A first attempt
Check every possible substring, and for each one test whether it has duplicates.
def longest_unique(s):
best = 0
for i in range(len(s)):
for j in range(i, len(s)):
if len(set(s[i:j + 1])) == j - i + 1: # rebuilds the set each time
best = max(best, j - i + 1)
return bestfunction longestUnique(s: string): number {
let best = 0;
for (let i = 0; i < s.length; i++) {
for (let j = i; j < s.length; j++) {
const seen = new Set(s.slice(i, j + 1)); // rebuilds each time
if (seen.size === j - i + 1) best = Math.max(best, j - i + 1);
}
}
return best;
}int longestUnique(String s) {
int best = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length(); j++) {
Set<Character> seen = new HashSet<>();
for (int x = i; x <= j; x++) seen.add(s.charAt(x)); // rebuilds
if (seen.size() == j - i + 1) best = Math.max(best, j - i + 1);
}
}
return best;
}int longestUnique(const char *s) {
int best = 0, n = strlen(s);
for (int i = 0; i < n; i++) {
int seen[256] = {0}, ok = 1;
for (int j = i; j < n; j++) {
unsigned char c = s[j];
if (seen[c]) { ok = 0; } /* duplicate breaks this start */
seen[c] = 1;
if (ok && j - i + 1 > best) best = j - i + 1;
}
}
return best;
}int longestUnique(const string& s) {
int best = 0;
for (int i = 0; i < (int)s.size(); i++) {
for (int j = i; j < (int)s.size(); j++) {
set<char> seen(s.begin() + i, s.begin() + j + 1); // rebuilds
if ((int)seen.size() == j - i + 1) best = max(best, j - i + 1);
}
}
return best;
}Two nested loops over positions, and the validity check adds more work — O(n²) at best,
O(n³) if you rebuild the set from scratch each time. Every restart throws away what the
previous window already learned.
The insight
Keep two independent edges, left and right. March right forward one step at a time,
absorbing each new character into the window. As long as the window stays valid, it grows and
you record its length. The instant it becomes invalid — a duplicate appears — advance left,
shrinking from the front, until the window is valid again.
The magic is that left only ever moves forward. It never rewinds. So across the whole
scan, right advances n times and left advances at most n times — 2n moves total.
The nested loop collapses into a single linear sweep.
Grow greedily, shrink only when forced
Expand the right edge every step. Shrink the left edge only enough to restore validity, never
more. Because neither pointer ever moves backward, each element enters and leaves the window
at most once — that's what makes it O(n).
How it works
Start empty
left = 0, right = 0, and an empty record of what's currently in the window (here, the set
of characters present).
Grow from the right
Read s[right]. If it isn't already in the window, add it — the window just got one longer.
Shrink from the left when invalid
If s[right] is a duplicate, remove s[left] from the window and advance left, repeating
until the duplicate is gone. Now the window is valid again.
Record and advance
The window [left, right] is valid, so update the best length with right - left + 1, then
move right forward and repeat to the end.
Watch the two edges chase across abcabcbb:
a b c a b c b b
[a] b c ... window "a" len 1
[a b] c ... window "ab" len 2
[a b c] a ... window "abc" len 3 ← best
a [b c a] b ... 'a' repeats → drop left → "bca" len 3
a b [c a b] c ... 'b' repeats → drop left → "cab" len 3The code
def longest_unique(s):
seen = set()
left = best = 0
for right, ch in enumerate(s):
while ch in seen: # shrink until ch is free to add
seen.remove(s[left])
left += 1
seen.add(ch)
best = max(best, right - left + 1)
return bestfunction longestUnique(s: string): number {
const seen = new Set<string>();
let left = 0, best = 0;
for (let right = 0; right < s.length; right++) {
const ch = s[right];
while (seen.has(ch)) { // shrink until ch is free
seen.delete(s[left]);
left++;
}
seen.add(ch);
best = Math.max(best, right - left + 1);
}
return best;
}int longestUnique(String s) {
Set<Character> seen = new HashSet<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
while (seen.contains(ch)) { // shrink until ch is free
seen.remove(s.charAt(left));
left++;
}
seen.add(ch);
best = Math.max(best, right - left + 1);
}
return best;
}int longestUnique(const char *s) {
int inWindow[256] = {0};
int left = 0, best = 0, n = strlen(s);
for (int right = 0; right < n; right++) {
unsigned char ch = s[right];
while (inWindow[ch]) { /* shrink until ch is free */
inWindow[(unsigned char)s[left]] = 0;
left++;
}
inWindow[ch] = 1;
int len = right - left + 1;
if (len > best) best = len;
}
return best;
}int longestUnique(const string& s) {
unordered_set<char> seen;
int left = 0, best = 0;
for (int right = 0; right < (int)s.size(); right++) {
char ch = s[right];
while (seen.count(ch)) { // shrink until ch is free
seen.erase(s[left]);
left++;
}
seen.insert(ch);
best = max(best, right - left + 1);
}
return best;
}Complexity
| Aspect | Cost | Why |
|---|---|---|
| Time | O(n) | right and left each advance at most n times, 2n total |
| Space | O(k) | the window record holds at most k distinct elements |
Here k is the alphabet size — for lowercase ASCII, O(k) is effectively O(1).
When to use it
Variable window = 'longest/shortest run satisfying a condition'
Reach for a variable window when the question is how long (or how short) a contiguous run
can be while some property holds: no repeats, sum ≤ target, at most k distinct values. The
condition must be monotonic — once the window is invalid, growing it further keeps it
invalid until you shrink — otherwise "only move left forward" breaks down.
Practice
Recap
- A variable-size window uses two forward-only edges: grow
rightgreedily, shrinkleftonly enough to restore validity. - Because neither pointer rewinds, each element enters and leaves once — an
O(n)scan even though awhilesits inside thefor. - It fits "longest/shortest contiguous run satisfying a monotonic condition"; the running record of the window's contents is what you check validity against.
How is this guide?
Last updated on