Самая длинная подстрока без повторов
Отслеживайте последние позиции в окне
«Самая длинная подстрока без повторов» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Классическая задача с окном
Найдите самую длинную подстроку без повторяющихся символов. Это одна из самых известных задач на скользящее окно, которая встречается почти в каждом проверяющем тестирование сервисе. 🔤
Ловушка полного перебора
Проверка повторов в каждой подстроке требует примерно O(n^2) или даже больше. Для длинных строк это слишком медленно, поэтому нужен более эффективный проход.
Окно уникальных символов
Поддерживайте окно, в котором всегда находятся различные символы. Расширяйте его справа, а при появлении повтора уменьшайте слева, пока повтор не исчезнет.
Запоминайте последние позиции
Храните последний индекс каждого символа в словаре. Так при проходе Вы мгновенно узнаете, где повтор встречался в последний раз.
last = {}
left = 0
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)Почему важна проверка
Проверка last[ch] >= left необходима. Без неё старая позиция за пределами окна ошибочно сдвинет левую границу назад.
Линейное время и линейная память
Каждый символ посещается один раз, а левая граница движется только вперёд, поэтому проход выполняется за O(n). Словарь использует память для хранения различных символов.
Учитывайте крайние случаи
Для пустой строки ответ равен нулю, а для строки из одного повторяющегося символа — единице. Проверьте оба случая перед отправкой решения, чтобы избежать коварного WA.
Повторно используемый шаблон
Словарь последних позиций вместе с левой границей, которая перепрыгивает вперёд, обобщается на многие задачи об уникальности, например на окна не более чем с одним повтором.
Быстрая проверка
Вы отслеживаете последний индекс каждого символа, находя самую длинную подстроку без повторов.
Итоги
Перемещайте окно уникальных символов, сохраняйте каждую последнюю позицию и перепрыгивайте левой границей повторы. Это решает классическую задачу за O(n). ✅
Часто задаваемые вопросы
Урок «Самая длинная подстрока без повторов» бесплатный?
Да — полный текст урока «Самая длинная подстрока без повторов» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Самая длинная подстрока без повторов»?
Отслеживайте последние позиции в окне Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Самая длинная подстрока без повторов»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Суммы окон фиксированного размера
- Окно переменного размера с двумя указателями
- Самая длинная подстрока без повторов
- Подсчёт окон, удовлетворяющих правилу