Sliding Window Visualization for Coding Interviews
Longest substring without repeats — window shrink/expand on conflict.
Concept
Sliding Window turns a family of 'find the best contiguous subarray/substring that satisfies X' problems from O(n^2) brute force into O(n). Instead of re-examining every [i, j] pair, you keep a mutable window [l, r] with a running aggregate — a sum, a count, a hashmap of character frequencies, a deque of maxima — and shrink or grow it by one element at a time so each index enters and leaves at most once. The pattern fits longest-substring-without-repeats, minimum-window-substring, max-sum-subarray-of-size-k, fruit-into-baskets, and any rate-limit or deduplication sweep where 'contiguous' is the key word. The tricky part is picking the invariant: fixed-size windows are easy, but variable-size windows need a clear rule for when to expand r vs when to contract l.
How it works
A variable-size sliding window advances r through the array, updates the running aggregate to include the new element, and then — while the aggregate violates the invariant — advances l and rolls the aggregate back. The critical property is that both l and r only ever move forward, so the total work is O(n) even though the inner while looks like a nested loop. You decide at each step whether the current window is 'valid' and, if so, record the answer (min length, max length, count, whatever the problem asks) before the next expansion. For a hashmap-backed window you usually track two counters: a map of current-window frequencies and a scalar 'matched' that says how many required characters hit their target count; the scalar lets you check validity in O(1) instead of diffing the whole map. Fixed-size windows are a simpler sub-case: you preload k elements, then for each subsequent r you add a[r] and remove a[r-k] in one step, keeping the aggregate exactly k wide. The failure mode to watch for is an aggregate that isn't reversible (e.g. max of a range), which is why monotonic deques exist — they let you evict the element leaving the window without recomputing the max from scratch.
Implementation
package dsa.slidingwindow;
import java.util.HashMap;
import java.util.Map;
public final class SlidingWindow {
// Longest substring without repeating characters.
public static int lengthOfLongestSubstring(String s) {
int[] lastSeen = new int[128];
for (int i = 0; i < 128; i++) lastSeen[i] = -1;
int best = 0, l = 0;
for (int r = 0; r < s.length(); r++) {
char c = s.charAt(r);
if (lastSeen[c] >= l) {
l = lastSeen[c] + 1;
}
lastSeen[c] = r;
best = Math.max(best, r - l + 1);
}
return best;
}
// Minimum window in s that contains all chars (with multiplicity) of t.
public static String minWindow(String s, String t) {
if (s == null || t == null || t.length() > s.length()) return "";
Map<Character, Integer> need = new HashMap<>();
for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
int required = need.size();
Map<Character, Integer> have = new HashMap<>();
int matched = 0;
int bestLen = Integer.MAX_VALUE, bestL = 0;
int l = 0;
for (int r = 0; r < s.length(); r++) {
char c = s.charAt(r);
if (need.containsKey(c)) {
have.merge(c, 1, Integer::sum);
if (have.get(c).intValue() == need.get(c).intValue()) matched++;
}
while (matched == required) {
if (r - l + 1 < bestLen) {
bestLen = r - l + 1;
bestL = l;
}
char lc = s.charAt(l);
if (need.containsKey(lc)) {
have.merge(lc, -1, Integer::sum);
if (have.get(lc) < need.get(lc)) matched--;
}
l++;
}
}
return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestL, bestL + bestLen);
}
}
Complexity
- Time:
O(n) — each index enters and leaves the window at most once - Space:
O(k) where k is the alphabet or distinct-keys bound (O(1) for ASCII)
Common pitfalls
- Comparing boxed Integer counts with == instead of intValue(), which fails for values above 127
- Moving l past r in the contraction loop and producing a negative window length
- Recording the answer after the contraction finishes instead of inside the valid-window while — loses tie cases
- Using max/min as the aggregate without a monotonic deque, forcing an O(k) rescan on every shrink
- Assuming the window keeps shrinking to empty — for longest-valid problems you must stop contracting before invariant breaks
Key design decisions & trade-offs
- Validity check — Chosen: Scalar 'matched' counter vs full map comparison. Scalar is O(1) per step but needs careful increment/decrement at the exact match boundary. Map-diff is simpler to reason about but O(k) per step.
- Alphabet storage — Chosen: int[128] fixed array vs HashMap<Character,Integer>. Array is ~5x faster and avoids autoboxing, but only works for bounded ASCII. HashMap generalizes to Unicode and arbitrary keys at a constant-factor cost.
- Window shape — Chosen: Variable vs fixed-k. Fixed-k is a one-liner when problem says 'of size k'; variable is required when validity depends on content, not length.
Practice problems
Interview follow-ups
- Solve sliding-window maximum in O(n) using a monotonic deque — why does the deque stay bounded?
- Extend minWindow to return all windows of minimum length, not just the first
- How does the window change when duplicates in t are allowed with exact multiplicity vs at-least multiplicity?
- Implement a rate limiter as a sliding window of timestamps — what does it cost in memory per user?
- Generalize to two-dimensional sliding windows for image convolutions
Why it matters
Sliding Window is a core part of the Arrays & Strings toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".