← all problems

Algorithm Shapes: The Sliding Window 🌶️🌶️🌶️ Challenge

Every algorithm you have seen so far either walks a string/array once (one loop) or checks every pair of positions (nested loops). A sliding window is a third shape: it walks the input ONCE, but keeps track of a window (a contiguous range marked by two edges, left and right) that grows and shrinks as it goes.

The pattern, for a problem like "find the longest contiguous range satisfying some rule":

  1. Move the RIGHT edge forward one step at a time, always including whatever is now inside the window.
  2. Whenever the window breaks the rule, move the LEFT edge forward (shrink) until the rule holds again.
  3. Every time the window is valid, compare it to the best one seen so far.

This is genuinely beyond what AP CS A requires, but it is one of the most useful techniques in real programming. Everything inside it (the loop, the comparisons) is built from tools you already have.

1. Why is checking every possible substring of a string of length n (a nested loop over every start and every end position) considered wasteful compared to a sliding window?

2. In the sliding window pattern above, what does "shrinking the window" (moving the left edge forward) actually accomplish?

3. Tracing "abcabcbb" for the longest substring with no repeated characters: the window grows to "abc" (indices 0-2), then the right edge reaches the second 'a' at index 3. What must happen now?

4. Continuing the same trace on "abcabcbb": after the window shrinks to handle the duplicate 'a', what is the length of the longest valid window found by the time the whole string has been processed?

5. A sliding window has what looks like a loop moving the right edge AND another loop (or condition) moving the left edge to shrink — so why is the total work still proportional to n, not n^2, the way two nested loops usually would be?

6. A sliding window implementation shrinks the left edge with if (lastSeen[c] > windowStart) instead of if (lastSeen[c] >= windowStart). What specifically goes wrong?

Your score for your class is recorded when you click Submit all — checking individual questions doesn't save it. You can submit again to improve your score; your best one counts.