Объясни скользящее окно
Вопрос
Объясни подход скользящего окна на задаче «самая длинная подстрока без повторов» и его сложность.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Называет признак: непрерывная подстрока плюс условие на её содержимое
Описывает, что хранится в окне (Map или Set символов)
Говорит, когда расширяем и когда сжимаем
Обновляет ответ, когда окно валидно
Объясняет O(n): каждый указатель проходит строку один раз
Что могут спросить следом
- Как ускорить сжатие через Map последнего индекса?
- Что поменяется, если разрешено до k повторов?
- Сколько памяти тратится и от чего зависит?
Разбор
Условие про непрерывную подстроку и ограничение на её содержимое, это сигнал окна. Держу два указателя l и r и Set символов текущего окна. На каждом шаге r добавляю символ; если он уже в окне, двигаю l вправо и удаляю символы, пока повтор не исчезнет. После этого окно без повторов, обновляю максимум длиной r - l + 1. Можно ускорить: хранить в Map последний индекс символа и прыгать l сразу на lastIndex + 1, если он внутри окна. Каждый указатель только растёт и проходит строку один раз, поэтому время O(n), память O(min(n, размер алфавита)).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.
Термины по теме
Ещё по теме «Скользящее окно»
- Самая длинная серия единиц с k заменами
- Перестановка как подстрока
- Самая длинная серия после k замен
- Самая длинная подстрока без повторов
- Максимальная сумма окна длины k
- Максимум гласных в окне
- Кратчайший подмассив с суммой ≥ target
- Самая короткая подстрока с k различными