Intermediate · Module 7 · Lesson 2
Variable-size window
Expand and shrink while maintaining a condition.
Lesson 38 of 123
1d streakVariable-Size Sliding Window: Monotonic Subarray Expansion & Shrinking
Variable-size sliding windows expand the right boundary to satisfy or maximize an objective, and contract the left boundary whenever a constraint is violated. Both pointers move strictly forward, guaranteeing amortized O(n) total time.
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> lastSeen = new HashMap<>();
int maxLen = 0, left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (lastSeen.containsKey(c)) {
left = Math.max(left, lastSeen.get(c) + 1); // Shrink window past duplicate
}
lastSeen.put(c, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}Active Recall Checkpoint
Why is Math.max(left, lastSeen.get(c) + 1) necessary rather than simply left = lastSeen.get(c) + 1?
Show answer & explanation
If the duplicate character occurred before the current left boundary, setting left directly would cause the left pointer to move backward, violating the monotonic window invariant.
Use it when
Use variable sliding windows for longest substring without repeating characters, minimum window substring, and longest subarray with sum <= target.
Reconsider when
Reconsider when negative numbers exist in sum constraints; negative numbers break window monotonicity (use prefix sum + hash map instead).
Cost Model
Complexity & Trade-offs
When to use it
- Contiguous subarrays or substrings with incrementally maintainable state.
- Longest, shortest, count, sum, or frequency constraints.
- Streaming range calculations.
Common mistakes
- Using a variable window when feasibility is not monotonic under shrinking.
- Adding an incoming item but forgetting to remove the outgoing one.
- Updating the answer before the window is valid.
Practice prompts
- Reproduce the worked Variable-size window example without looking at the trace.
- Change one input condition and explain whether the Variable-size window invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check