Окно, которое помнит своё содержимое

Нужен самый длинный отрезок текста, в котором не больше 2 разных букв. Для "eceba" ответ "ece", длина 3.

В прошлом уроке окно хранило одно число, сумму. Одним числом на этот вопрос не ответить. Условие «не больше 2 разных букв» касается содержимого окна: какие буквы в нём есть и сколько каждой. Сумма тут ничего не скажет. Окно должно помнить, что в нём лежит.

Так же устроен ограничитель частоты (программа, которая не даёт клиенту слать запросы слишком часто). Он спрашивает: сколько запросов этот клиент сделал за последние 60 секунд? Это подсчёт того, что сейчас лежит в движущемся окне времени.

Теперь правило касается того, что лежит внутри отрезка. Например: «не больше 2 разных букв одновременно». Одна сумма на это не ответит. Нужно знать, какие буквы есть в окне и сколько каждой.

Поэтому ты ведёшь счёт для каждой буквы. Возьми "eceba". Окно "ece": e две штуки, c одна, разных букв 2, всё в порядке. Добавляешь b, разных букв стало 3. Тогда убираешь буквы слева, пока одна из букв не исчезнет из окна совсем. Убрал первую e: e осталась одна, разных по-прежнему 3. Убрал c: её счёт стал 0, c ушла из окна. Разных снова 2. Число разных букв в счёте и есть то, что ты сверяешь с правилом, когда расширяешь и сужаешь окно.

Храни Map (таблицу «ключ → счётчик», из урока про Map) для элементов, которые сейчас в окне. Когда right добавляет элемент в окно, увеличь его счётчик. Когда left убирает элемент, уменьши счётчик. Если счётчик дошёл до нуля, удали ключ. Тогда map.size (число ключей в Map) равен числу разных значений в окне. С этим числом ты и сверяешь правило.

Удалять ключ на нуле обязательно. Допустим, ключ со счётчиком 0 остался в Map. Тогда map.size посчитает букву, которой в окне уже нет. Проверка на число разных букв ошибётся, и окно станет шире, чем можно.

Порядок такой. Сдвигай right и увеличивай счётчик. Пока в окне слишком много разных значений, убирай элемент слева и уменьшай его счётчик, удаляя ключ на нуле. Когда правило снова выполняется, записывай длину окна.

Проследим «самый длинный отрезок, где не больше 2 разных букв» на "eceba".

• Добавили e: {e:1}, длина 1.
• Добавили c: {e:1, c:1}, длина 2.
• Добавили e: {e:2, c:1}, длина 3 ("ece").
• Добавили b: разных стало 3. Убрали слева e: {e:1, c:1, b:1}, разных всё ещё 3. Убрали c: {e:1, b:1}, разных 2. Окно "eb", длина 2.
• Добавили a: разных снова 3. Убрали e: {b:1, a:1}. Окно "ba", длина 2.

Лучшая длина 3.

Время O(n). right добавляет каждый элемент один раз, left убирает каждый не больше одного раза. Каждая операция с Map занимает примерно один шаг. Память O(k): в Map лежит не больше ключей, чем разных значений может быть в окне. Это число ограничено K или размером алфавита (числом всех возможных букв).

Ограничители частоты запросов к API и защита от злоупотреблений ведут счётчики в скользящем окне для каждого клиента или адреса. Мониторинг следит за правилом «не больше K разных пользователей или IP-адресов за окно». Поиск самой длинной подстроки без повторов использует то же окно с более строгим правилом. Если решение для движущегося окна зависит от того, какие элементы в нём лежат и сколько каждого, окно хранит Map именно так.