Найдите длину самой длинной подстроки без повторяющихся символов. Объясните технику скользящего окна и когда она применима.
Короткий ответ
- Перебор всех подстрок — O(n^2) и хуже, окно даёт O(n)
- Два указателя: правый расширяет окно, левый сжимает
- Словарь хранит последний индекс каждого символа
- Повтор внутри окна — левый край прыгает за прошлое вхождение
- Проверка last[ch] >= left отличает повтор в окне от старого
- Левый указатель не откатывается — каждый символ обработан дважды максимум
- Техника работает, когда свойство окна монотонно при сжатии
Скользящее окно со словарём последних индексов решает задачу за O(n) по времени и O(k) по памяти, где k — размер алфавита.
Как сказать вслух
пример ответаЯ держу окно без повторов двумя указателями и расширяю его правым краем. Встретив символ, который уже есть в окне, передвигаю левый край сразу за его прошлое вхождение — для этого храню последний индекс каждого символа. Оба указателя идут только вперёд, поэтому проход линейный.
Подробный ответ
Основной ответ
Окно [left, right] поддерживает инвариант «внутри нет повторов». Правый край движется по строке; для каждого символа словарь last хранит индекс его последнего вхождения. Если символ уже встречался и его прошлый индекс не левее left — повтор внутри окна: переносим left на last[ch] + 1 одним прыжком. Проверка last[ch] >= left обязательна: без неё старое вхождение, уже выкинутое из окна, ошибочно сдвинет left назад или заставит сжимать зря. После обновления записываем last[ch] = right и обновляем максимум длины right - left + 1. Оба указателя монотонно растут — O(n) времени, память O(k) по алфавиту. Общий шаблон скользящего окна: расширяем правым краем, при нарушении свойства сжимаем левым; применим, когда нарушенное свойство не восстанавливается расширением (монотонность).
Ключевые моменты
- Почему O(n). Левый и правый указатели только увеличиваются, суммарно не более 2n шагов — амортизированная линейность.
- Прыжок левого края. Хранение последнего индекса позволяет перепрыгнуть сразу за повтор вместо посимвольного сжатия — код короче и быстрее.
- Условие last[ch] >= left. Индекс в словаре может указывать на символ левее окна; двигать left назад нельзя, это ломает инвариант.
- Когда окно применимо. Нужна монотонность: если окно нарушает условие, любое его расширение тоже нарушает — тогда сжатие корректно; для задач без монотонности окно не работает.
Практический контекст
Скользящее окно — обязательная техника: на ней строятся задачи про минимальное окно с покрытием строки, максимум суммы подмассива длины k, самую длинную подстроку с k различными символами. Интервьюер смотрит, понимаете ли вы, почему сложность линейна, и не путаетесь ли в условии сдвига левого края. Проговорите крайние случаи: пустая строка, строка без повторов, строка из одного символа.
Пример кода
def longest_unique_substring(s):
last = {} # символ -> индекс последнего вхождения
left = best = 0
for right, ch in enumerate(s):
if ch in last and last[ch] >= left: # повтор внутри окна
left = last[ch] + 1 # прыжок за прошлое вхождение
last[ch] = right
best = max(best, right - left + 1)
return best
assert longest_unique_substring('abcabcbb') == 3 # 'abc'
assert longest_unique_substring('bbbbb') == 1
assert longest_unique_substring('pwwkew') == 3 # 'wke'
assert longest_unique_substring('') == 0
assert longest_unique_substring('abba') == 2Частые ошибки
- Двигают left назад, когда найденный повтор лежит левее текущего окна
- Сжимают окно по одному символу в цикле там, где возможен прямой прыжок, и усложняют код
- Обновляют ответ до восстановления инварианта окна и завышают длину