Выбор ответа Middle Скользящее окно спрашивают часто обновлено
Подстрока без повторов
Вопрос
Самая длинная подстрока без повторяющихся символов. Какой подход оптимален?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Окно: расширяем справа, при повторе сдвигаем левый край. Правый указатель добавляет символ; если он уже в окне, левый двигается, пока повтор не уйдёт (или прыгает сразу за прошлое вхождение через Map).
Варианты ответа
- Окно: расширяем справа, при повторе сдвигаем левый крайправильный ответ
- Перебрать все подстроки и проверить каждую через Set
- Отсортировать символы и найти самый длинный уникальный отрезок
- Префиксные суммы по кодам символов и сравнение отрезков
Разбор
Правый указатель добавляет символ; если он уже в окне, левый двигается, пока повтор не уйдёт (или прыгает сразу за прошлое вхождение через Map). Каждый символ входит и выходит один раз: O(n).
- Перебор подстрок O(n²) и больше.
- Сортировка теряет порядок, а подстрока должна быть непрерывной.
- Префиксные суммы считают суммы, а не уникальность.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.
Термины по теме
Ещё по теме «Скользящее окно»
- Самая длинная серия единиц с k заменами
- Перестановка как подстрока
- Самая длинная серия после k замен
- Самая длинная подстрока без повторов
- Максимальная сумма окна длины k
- Максимум гласных в окне
- Кратчайший подмассив с суммой ≥ target
- Самая короткая подстрока с k различными