Паттерн: Скользящее окно

Признак в условии

• «непрерывный участок» массива или строки - подряд, не подпоследовательность
• «самый длинный / самый короткий, при условии …»
• «не более K различных», «ровно K», «сумма не меньше target»

Идея

Окно [left, right]. Расширяем right всегда, чиним left, пока условие нарушено. Ответ записываем там, где окно допустимо. Каждый индекс входит и выходит из окна максимум по разу - отсюда O(n), несмотря на вложенный while.

Шаблон

let left = 0, best = 0;
const count = new Map();
for (let right = 0; right < s.length; right++) {
  add(s[right], count);
  while (!ok(count)) {           // окно испортилось: чиним слева
    remove(s[left], count);
    left++;
  }
  best = Math.max(best, right - left + 1);
}

Сложность

Время O(n), память O(размер алфавита) или O(k).

Частые ошибки

• отрицательные числа: сумма перестаёт быть монотонной, окно не работает - нужны префиксные суммы
• нулевые счётчики не удаляются из Map, и size перестаёт отражать число различных
• ответ фиксируется вне проверки условия
• left уезжает назад (при работе с «последней позицией символа» двигать только вперёд)

Мнемоника

«Расширяй справа, чини слева, записывай ответ»

Не путать с

• Два указателя - оба двигают два индекса, но у окна между ними непрерывный участок, который что-то накапливает; у двух указателей между ними ничего нет, они просто сходятся
• Префиксные суммы - окно годится, когда числа неотрицательные и сумма монотонна. Появились отрицательные - окно ломается, нужны префиксные суммы с хеш-таблицей
• Хеш-таблица - если участок не обязан быть непрерывным, окна нет - есть просто подсчёт

Задачи на этот паттерн

• самая длинная подстрока без повторов
• максимальная сумма окна длины k
• самая короткая подстрока с k различными
• кратчайший подмассив с суммой ≥ target
• максимум гласных в окне
• самая длинная серия после k замен
• перестановка как подстрока
• самая длинная серия единиц с k заменами

Суть

Окно это отрезок [l, r]. Правый край добавляет элемент, левый убирает. Состояние окна (сумма, частоты символов) обновляется за O(1), поэтому вместо перебора всех подмассивов O(n²) получаем O(n).

Как распознать по условию

• «подмассив» или «подстрока» (то есть непрерывный кусок);
• «самый длинный / самый короткий / количество» с условием;
• «ровно k подряд идущих элементов»;
• условие монотонно: расширение окна только ухудшает (или только улучшает) его.

Окно фиксированной длины

function maxSumK(arr, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) sum += arr[i];
  let best = sum;
  for (let i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i - k];   // вошёл i, вышел i - k
    best = Math.max(best, sum);
  }
  return best;
}

Окно переменной длины

Шаблон «расширяй справа, сжимай слева, пока условие нарушено»:

function longestUnique(s) {
  const inWin = new Set();
  let l = 0, best = 0;
  for (let r = 0; r < s.length; r++) {
    while (inWin.has(s[r])) inWin.delete(s[l++]);
    inWin.add(s[r]);
    best = Math.max(best, r - l + 1);  // окно валидно
  }
  return best;
}

Для «самого короткого окна» наоборот: пока окно валидно, обновляем ответ и сжимаем.

Почему O(n)

Вложенный while пугает, но l только растёт. За всё время он сдвинется не больше n раз, r тоже. Итого 2n шагов.

Когда окно не работает

Если в массиве есть отрицательные числа, сумма окна не монотонна: сжатие может её увеличить. Задачи «подмассив с суммой k» с отрицательными числами решают префиксными суммами и Map (см. модуль «Префиксные суммы»).

Ловушки

• Обновлять ответ до того, как окно стало валидным.
• Длина окна это r - l + 1, а не r - l.
• Set вместо Map-счётчика, когда важны повторы (анаграммы).
• Применять к подпоследовательностям (не непрерывным): там нужна динамика.

Что спросят на собесе

• Найди самую длинную подстроку без повторов.
• Почему вложенный цикл не делает решение квадратичным?
• Когда окно не подходит?
• Как найти все анаграммы строки p в s?