Sliding Window

How to recognize it

Sliding window questions describe a contiguous range with a constraint: the longest substring without repeating characters, the smallest subarray with a sum at least K, the number of substrings with at most two distinct characters. The word "contiguous" (or its implicit presence — "subarray" and "substring" both imply it, while "subsequence" does not) is the tell. If elements can be skipped and still count, you are looking at a different pattern, usually dynamic programming.

How the pattern works

The general shape: maintain a window with a left and right edge. Expand the right edge, updating whatever state describes the window's contents (a running sum, a character frequency map). When the window violates the constraint, shrink from the left until it is valid again. Track the best window seen along the way.

def longest_unique_substring(s):
    seen = set()
    left = 0
    best = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        best = max(best, right - left + 1)
    return best

function longestUniqueSubstring(s) {
  const seen = new Set();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }
    seen.add(s[right]);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Narrate the invariant explicitly: "the window from left to right always contains only unique characters — when I hit a duplicate, I shrink from the left until it's unique again." Stating the invariant is what convinces an interviewer the approach is correct, rather than something that happens to pass the visible test cases.

Common mistakes

• Using a nested loop to re-check the window from scratch every time it expands — the whole point of sliding window is that each element enters and leaves the window at most once, giving O(n) total, not O(n²)
• Forgetting to update the tracked state (sum, frequency map, distinct count) symmetrically on both expand and shrink
• Confusing "at most K" with "exactly K" distinct elements — these require different shrink conditions and are a common source of off-by-one bugs
• Not clarifying whether an empty window or single-element window is a valid answer before coding the edge cases

Complexity

A correct sliding window is O(n) time because each pointer moves forward at most n times total — even though there are two nested loops in the code, they do not multiply, since the inner loop's total iterations across the whole run are bounded by n. This is a common point of confusion worth stating explicitly: "it looks like a nested loop, but left only ever moves forward, so the total work across all iterations is O(n), not O(n²)." Space is O(k) where k is the size of the tracked state (the character set, for example). See Time & Space Complexity for more on defending an amortized-complexity claim like this one.