Скользящее окно

Окно — это текущий непрерывный фрагмент

Если задача говорит о последовательных символах строки, часто не нужно заново обрабатывать каждый возможный фрагмент. Можно хранить границы текущего окна и обновлять только то, что изменилось после его сдвига.

Для окна фиксированной длины правый край добавляет новый символ, а когда размер становится больше нужного, символ с левого края перестаёт учитываться.

Фиксированное окно

Пусть нужно найти максимальное количество гласных среди всех фрагментов длины k. Вместо подсчёта каждого фрагмента с нуля достаточно поддерживать число гласных в текущем окне.

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);
    }
}

Каждый символ добавляется в окно один раз и удаляется из него не более одного раза, поэтому при постоянной стоимости обновления весь проход занимает O(n).

Переменное окно

Иногда длина заранее неизвестна. Тогда правый край расширяет окно, а левый двигается только тогда, когда текущее состояние перестаёт удовлетворять условию задачи. Обычно внутри окна дополнительно поддерживается счётчик, сумма или таблица частот.

Ключевой вопрос при таком подходе: можно ли после добавления или удаления одного символа быстро обновить состояние окна. Если да, два вложенных движения границ часто всё равно дают линейное время, потому что каждая граница проходит строку только слева направо.