Slide a contiguous window and update its state using only the value entering and the value leaving. Avoid recomputing the entire window from scratch.
A sliding-window simulator for range sums and duplicate-free substrings
Choose a mode and compare examples. Orange marks the current window; green marks the best window found so far.
Fixed-size windows
Recomputing every length-k sum takes O(nk). Sliding changes only two values, so one addition and one subtraction per step gives O(n). Compare the operation counters.
Variable-size windows
Expand r; when a condition such as uniqueness is violated, advance l until it holds again. A dictionary or frequency array tracks the window. Here last records the most recent index of each character, allowing l to jump past a duplicate directly.
Common coding exercises
Examples include maximum sum or average over k values, longest unique substring, minimum covering window, and longest interval with at most k distinct values. For the maximum element in each length-k window, use a monotonic deque.