Expanding the Window

The right pointer is the discovery pointer. Every time it moves, the algorithm learns what happens when one more element joins the current contiguous range. That new element can improve an aggregate, create a violation, satisfy a missing requirement, or unlock many windows ending at the same position.

A reliable mental model is to process the array as a stream. At each step, the next item arrives on the right. You update the window state immediately, then decide whether the current range is valid, invalid, complete, or worth shrinking.

You grow when you still need more information. For longest-valid problems, every position should be tried as a possible right end because a later element may produce a longer range. For shortest-covering problems, you grow until the window finally satisfies all required conditions. For counting-at-most problems, each expansion creates a batch of valid suffixes after repair.

Growth should be monotonic. Do not reset right back to left + 1 for every start index. That recreates the quadratic brute force. Sliding window earns linear time by letting each right endpoint enter exactly once.

Expansion must update every piece of state that depends on membership. Add to the sum, increment the character count, insert into the map, update the number of distinct keys, or push into the deque. If a later shrink removes the element, the inverse update should be equally clear.

This symmetry is important for correctness. If entering a value increments distinct when its count becomes one, leaving a value must decrement distinct when its count becomes zero. A broken inverse update usually causes windows to appear valid or invalid long after the boundaries have moved.

The most common mistake is updating the answer too early. If expansion can make the window invalid, wait until after the shrink loop before recording a longest-valid length. Another mistake is expanding only while the current window is valid; that can skip right endpoints that become valid again after shrinking.

A third mistake is assuming growth always improves the answer. For shortest-window problems, growth is necessary to reach validity, but the answer is usually improved by shrinking after the requirement is met.