Variable-Size Sliding Window — Longest Substring Without Repeating Characters
Two pointers, one pass, O(n) — learn how the variable-size sliding window grows and shrinks to solve substring and subarray problems efficiently.
Variable-Size Sliding Window — Longest Substring Without Repeating Characters
You've seen sliding window with a fixed size — the window just marches through the array like a train car. The variable-size version is different. The window grows when things are going well and shrinks when a constraint gets violated. It expands from the right, collapses from the left, and never goes backward. Two pointers, one pass, O(n).
If you can internalize that both pointers only ever move forward — meaning the total number of pointer moves is at most 2n — you'll never second-guess the complexity again.
The Pattern
You maintain a window [left, right] that satisfies some constraint (no duplicate characters, sum ≤ target, at most k distinct values, etc.). The right pointer expands the window on every step. The left pointer only moves when the constraint is violated — and only moves far enough to restore it.
Problem 1: Longest Substring Without Repeating Characters
LeetCode 3 — find the length of the longest substring with no repeated characters.
s = "abcabcbb"
Output: 3 (substring "abc")Brute Force — O(n²) Time, O(min(n, alphabet)) Space
Check every possible substring. For each starting position, extend until you hit a duplicate.
// Input: s = "abcabcbb"
// Output: 3
const lengthOfLongestSubstringBrute = (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; // Duplicate — this window is done
seen.add(s[end]);
maxLen = Math.max(maxLen, end - start + 1);
}
}
return maxLen;
};
// Time: O(n²) | Space: O(min(n, alphabet))Works, but you're rebuilding the Set from scratch on each outer iteration. For "abcabcbb", you process a, b, c three separate times.
Sliding Window with Set — O(n) Time, O(min(n, alphabet)) Space
One window that shrinks from the left when a duplicate enters.
// Input: s = "abcabcbb"
// Output: 3
const lengthOfLongestSubstringSet = (s) => {
const windowChars = new Set();
let left = 0;
let maxLen = 0;
for (let right = 0; right < s.length; right++) {
// Shrink from left until the window no longer contains s[right]
while (windowChars.has(s[right])) {
windowChars.delete(s[left]);
left++;
}
windowChars.add(s[right]);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
};
// Time: O(n) | Space: O(min(n, alphabet))This works but has a subtle inefficiency: if s[right] is a duplicate that appeared far back in the window, you shrink one character at a time until you reach it. That can be multiple steps.
Sliding Window with Map — O(n) Time, O(min(n, alphabet)) Space
Store the last seen index of each character. When a duplicate appears, jump left directly past the previous occurrence — no slow shrink.
// Input: s = "abcabcbb"
// Output: 3
const lengthOfLongestSubstring = (s) => {
const lastSeen = new Map(); // char → last index it appeared
let left = 0;
let maxLen = 0;
for (let right = 0; right < s.length; right++) {
const char = s[right];
// If duplicate is inside the current window, jump left past it
if (lastSeen.has(char) && lastSeen.get(char) >= left) {
left = lastSeen.get(char) + 1;
}
lastSeen.set(char, right); // Always update to the latest index
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
};
// Time: O(n) | Space: O(min(n, alphabet))lastSeen.get(char) >= left is not optional. The map keeps stale entries from before the current window. Without this check, you might move left backward when a character reappears that's outside the current window. That would break everything.Tracing through "abcabcbb":
right=0: 'a' → lastSeen={a:0}, window=[0..0], len=1
right=1: 'b' → lastSeen={a:0, b:1}, window=[0..1], len=2
right=2: 'c' → lastSeen={a:0, b:1, c:2}, window=[0..2], len=3
right=3: 'a' → lastSeen has 'a' at 0, 0 >= left(0) → left=1
lastSeen={a:3, b:1, c:2}, window=[1..3], len=3
right=4: 'b' → lastSeen has 'b' at 1, 1 >= left(1) → left=2
lastSeen={a:3, b:4, c:2}, window=[2..4], len=3
right=5: 'c' → lastSeen has 'c' at 2, 2 >= left(2) → left=3
window=[3..5], len=3
right=6: 'b' → lastSeen has 'b' at 4, 4 >= left(3) → left=5
window=[5..6], len=2
right=7: 'b' → lastSeen has 'b' at 6, 6 >= left(5) → left=7
window=[7..7], len=1
maxLen = 3 ✓Problem 2: Longest Repeating Character Replacement
LeetCode 424 — given a string and k, you can replace at most k characters. Find the longest substring you can make with all the same character.
s = "AABABBA", k = 1
Output: 4 (replace the 'B' at index 4 → "AABAAAA")The key insight: a window is valid if (window length) - (count of most frequent char in window) ≤ k. In other words, the number of characters you'd need to replace equals window size minus the dominant character's count. If that exceeds k, shrink.
// Input: s = "AABABBA", k = 1
// Output: 4
const characterReplacement = (s, k) => {
const charCount = new Array(26).fill(0);
const A = 'A'.charCodeAt(0);
let left = 0;
let maxFreq = 0; // Max frequency of any single char in current window
let maxLen = 0;
for (let right = 0; right < s.length; right++) {
const charIndex = s.charCodeAt(right) - A;
charCount[charIndex]++;
maxFreq = Math.max(maxFreq, charCount[charIndex]);
// Window is invalid if replacements needed > k
const replacementsNeeded = (right - left + 1) - maxFreq;
if (replacementsNeeded > k) {
// Shrink by one — don't update maxFreq (see tip below)
charCount[s.charCodeAt(left) - A]--;
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
};
// Time: O(n) | Space: O(1) — 26-char alphabet is constantmaxFreq when shrinking. This is intentional: we don't need the exact current max frequency — we just need to know if we've beaten our previous best window. maxFreq only needs to go up, not down, because we're looking for the longest valid window, not every valid window.Problem 3: Minimum Window Substring
LeetCode 76 — given strings s and t, find the smallest substring of s containing all characters of t.
s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"This one's harder. You need to track how many distinct character requirements are currently satisfied.
// Input: s = "ADOBECODEBANC", t = "ABC"
// Output: "BANC"
const minWindow = (s, t) => {
if (t.length > s.length) return "";
// Build frequency map for target characters
const need = new Map();
for (const char of t) {
need.set(char, (need.get(char) || 0) + 1);
}
const window = new Map();
let left = 0;
let satisfied = 0; // How many unique chars in t are fully covered
const required = need.size; // Unique chars in t we need to satisfy
let minLen = Infinity;
let minStart = 0;
for (let right = 0; right < s.length; right++) {
const char = s[right];
window.set(char, (window.get(char) || 0) + 1);
// Check if this char's requirement is now met
if (need.has(char) && window.get(char) === need.get(char)) {
satisfied++;
}
// Shrink from left as long as all requirements are satisfied
while (satisfied === required) {
const windowLen = right - left + 1;
if (windowLen < minLen) {
minLen = windowLen;
minStart = left;
}
// Remove leftmost char from window
const leftChar = s[left];
window.set(leftChar, window.get(leftChar) - 1);
if (need.has(leftChar) && window.get(leftChar) < need.get(leftChar)) {
satisfied--; // Requirement no longer met — exit inner loop
}
left++;
}
}
return minLen === Infinity ? "" : s.slice(minStart, minStart + minLen);
};
// Time: O(s + t) | Space: O(s + t)The structure here flips from the previous problems: instead of shrinking when the window is invalid, you shrink when the window is valid to find the smallest one. The inner while loop runs until the window is no longer satisfying all requirements.
satisfied counter is the efficient way to check "is all of t covered?" without iterating over the entire need map on every step. It ticks up when a character reaches its exact required count, and ticks down when the count drops below.Complexity Cheat Sheet
| Problem | Approach | Time | Space |
|---|---|---|---|
| Longest Substring No Repeat | Brute Force | O(n²) | O(alphabet) |
| Longest Substring No Repeat | Sliding Window (Set) | O(n) | O(alphabet) |
| Longest Substring No Repeat | Sliding Window (Map) | O(n) | O(alphabet) |
| Longest Repeating Char Replacement | Sliding Window | O(n) | O(1) |
| Minimum Window Substring | Sliding Window | O(s + t) | O(s + t) |
Interview Tips
Identify whether your window shrinks or grows based on validity. Most sliding window problems fall into one of two shapes: (1) "find the longest window that's always valid" — expand right, shrink left when invalid; (2) "find the shortest window that's valid" — expand right, shrink left while valid. Before coding, figure out which shape you're dealing with.
The lastSeen.get(char) >= left guard is a common stumbling point. If an interviewer asks why it's there, explain that the map persists entries from previous windows. Without the guard, a character that appeared before left could incorrectly trigger a window shrink. It's a subtle bug that only shows up on inputs like "tmmzuxt".
Draw the window state, not the code. When you're stuck, annotate a small example: left=X, right=Y, window=[...]. Interviewers find this impressive because it shows you're reasoning about state, not just typing. It also catches off-by-one errors before they become bugs.
Comments (0)
No comments yet. Be the first to share your thoughts!
Related Articles
