01 Идея
Вместо перебора всех подстрок мы один раз проходим по строке от начала до конца. Для каждого символа решаем: продолжает ли он текущую «правильную» цепочку или нет.
Переменная count хранит длину текущей правильной цепочки. Если новый символ подходит — увеличиваем count. Если не подходит — сбрасываем в 0 (или в 1, если символ сам может начать новую цепочку).
уже обработано ← count → c ещё не смотрели
■ ■ ■ ■ ■ ■ ■ [ ✓ ✓ ✓ ✓ ✓ ] ? □ □ □ □ □
Что делаем на каждом шаге?
Символ подходит? → count += 1
Не подходит? → сохраняем max, сбрасываем count
В конце: max(maxLen, count)
Почему это быстро?
Каждый символ обрабатывается ровно один раз
Нет вложенных циклов
Сложность: O(n) — линейная
💡 Ключевая идея Не нужно перебирать все подстроки (это O(n²)). Достаточно одного прохода с двумя переменными: count (текущая длина) и maxLen (лучший результат).
02 Шаблон кода
Вот универсальный шаблон. Меняется только условие в if — всё остальное одинаковое для любой задачи:
def solve(s):
maxLen = 0
count = 0
for c in s:
if <цепочка продолжается>:
count += 1
maxLen = max(count, maxLen)
else:
count = 0 # или 1, если c может начать новую цепочку
return maxLen
⚠️ Умный сброс При несовпадении не всегда count = 0. Если текущий символ сам может начать новую цепочку, ставим count = 1. Например, ищем цепочку из «A»: встретили «B» → count = 0. Но если ищем чередование AB и встретили «A» вместо «B» — это начало нового паттерна → count = 1.
03 Примеры условий
Одна и та же структура кода, разные условия продолжения цепочки:
| Задача |
Условие в if |
Сброс |
| Цепочка из букв «A» |
c == 'A' |
count = 0 |
| Цепочка из гласных |
c in 'AEIOU' |
count = 0 |
| Цепочка из цифр |
c.isdigit() |
count = 0 |
| Цепочка без пробелов |
c != ' ' |
count = 0 |
| Паттерн AB (чередование) |
c == pattern[count % n] |
count = 1 или 0 |
04 Симулятор
Выберите задачу, введите строку, затем нажимайте «Шаг» или «Запустить», чтобы пошагово увидеть работу алгоритма.
Попробуй · интерактивный симулятор
Задача
Условие: c == 'A'
Нажми «Шаг» или «Запустить», чтобы начать
05 Живая трассировка
Введите любую строку, выберите условие — таблица трассировки построится автоматически. Нажмите на любую строку таблицы, чтобы подсветить шаг.
Попробуй · интерактивная трассировка
Условие
| № |
Символ |
Подходит? |
Действие |
count |
maxLen |
06 Конкретные решения
Вот как выглядит шаблон для каждой из задач:
Цепочка из букв «A»
for c in s:
if c == 'A':
count += 1
maxLen = max(count, maxLen)
else:
count = 0
Цепочка из гласных
for c in s:
if c in 'AEIOU':
count += 1
maxLen = max(count, maxLen)
else:
count = 0
Цепочка из цифр
for c in s:
if c.isdigit():
count += 1
maxLen = max(count, maxLen)
else:
count = 0
07 Ключевые идеи
Один проход
Проходим строку слева направо один раз. Сложность O(n).
Два счётчика
count — текущая цепочка, maxLen — лучший результат. В конце: maxLen.
Сброс
При несовпадении: count = 0. Но если символ начинает новую цепочку — count = 1.
Меняем только условие
Шаблон один и тот же. Для новой задачи достаточно изменить условие в if.
Шпаргалка
| Элемент |
Описание |
count |
Длина текущей найденной цепочки |
maxLen |
Максимальная длина, найденная за весь проход |
if <условие> |
Проверяем, подходит ли текущий символ |
| Сброс |
count = 0 (или 1, если символ начинает новую цепочку) |
| Обновление max |
maxLen = max(count, maxLen) при каждом совпадении |
| Сложность |
O(n) — один проход, без вложенных циклов |