A strong answer
A sliding window handles problems about contiguous subarrays or substrings by keeping two indexes, left and right, that only move forward, plus a summary of the window (a sum, counts, a set) that is updated in O(1) as elements enter and leave. Because neither end moves backward, the total work is O(n).
There are two templates. A fixed window of size k adds one element and removes one per step: maximum sum of k consecutive values, anagram search. A variable window extends right and then shrinks from the left while the window violates the condition (for longest problems), or shrinks while it still satisfies it (for shortest problems).
The variable window is correct only when the condition is monotonic in the window's extent: if a window is invalid, every window containing it is invalid too. "No repeated character", "at most k distinct values" and "sum ≤ S with non-negative numbers" qualify. That is what justifies discarding all windows starting at the old left index at once.
It fails when that monotonicity fails. With negative numbers, extending a window can lower its sum, so "sum exactly k" or "sum at least k" can't be solved by shrinking. Then I would use prefix sums: for counting subarrays with sum k, a hash map of earlier prefix sums; for the shortest subarray with sum at least k, prefix sums with a monotonic deque. Some "exactly k" problems can still use windows indirectly: count(exactly k) = count(at most k) − count(at most k − 1).
What the interviewer is listening for
- Both templates and the O(n) amortized argument.
- The monotonicity requirement, stated clearly.
- What to do when it doesn't hold, with prefix sums as the main alternative.
Common mistakes
- Applying a window to sums with negative numbers.
- Recomputing the summary from scratch each step, which makes it O(n·k).
- Confusing substrings with subsequences, which aren't contiguous.