Sliding Window

A window is the current contiguous fragment

If a problem talks about consecutive characters of a string, we often do not need to process every possible fragment from scratch. Instead, we can maintain the boundaries of the current window and update only what changed after it moved.

For a fixed-size window, the right boundary adds a new character, and once the size becomes larger than required, the character at the left boundary stops contributing.

A fixed-size window

Suppose we need to find the maximum number of vowels among all fragments of length k. Instead of recounting each fragment from scratch, we only maintain the vowel count in the current window.

int vowels = 0;
int best = 0;

for (int right = 0; right < text.length(); right++) {
    if ("aeiou".indexOf(text.charAt(right)) >= 0) {
        vowels++;
    }

    if (right >= k && "aeiou".indexOf(text.charAt(right - k)) >= 0) {
        vowels--;
    }

    if (right >= k - 1) {
        best = Math.max(best, vowels);
    }
}

Each character enters the window once and leaves it at most once, so with constant-time updates the whole pass takes O(n).

A variable-size window

Sometimes the length is not known in advance. Then the right boundary expands the window, while the left boundary moves only when the current state stops satisfying the problem condition. A counter, sum, or frequency table is often maintained inside the window as well.

The key question for this approach is whether the window state can be updated quickly after adding or removing one character. If it can, two nested boundary movements can still give linear time, because each boundary crosses the string only from left to right.