Выбор ответа Senior Скользящее окно обновлено
Минимальное окно: условие сжатия
Вопрос
Задача: минимальная подстрока s, содержащая все символы t с учётом повторов. Когда сжимать окно слева?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Пока окно покрывает все символы t с повторами, обновляя ответ. Держим missing: сколько символов t ещё не покрыто.
Варианты ответа
- Всегда сразу после добавления очередного символа справа
- Пока окно покрывает все символы
tс повторами, обновляя ответправильный ответ - Только когда длина окна стала больше
t.length - Когда встретили символ, которого нет в строке
t
Разбор
Держим missing: сколько символов t ещё не покрыто. Пока missing === 0, окно валидно: записываем ответ и сдвигаем левый край. Как только окно перестало покрывать t, расширяем вправо. O(|s| + |t|).
- Сжатие всегда потеряет валидные окна.
- Длина больше
t.lengthне гарантирует покрытия. - Лишние символы внутри окна допустимы.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.
Термины по теме
Ещё по теме «Скользящее окно»
- Самая длинная серия единиц с k заменами
- Перестановка как подстрока
- Самая длинная серия после k замен
- Самая длинная подстрока без повторов
- Максимальная сумма окна длины k
- Максимум гласных в окне
- Кратчайший подмассив с суммой ≥ target
- Самая короткая подстрока с k различными