Почему не перебрать все подстроки?

Для строки из миллиона символов подстрок около 5·10¹¹, программа не успеет. Один проход занимает доли секунды.

Что такое метод двух указателей?

Окно между двумя индексами: правый идёт вперёд, левый догоняет его, когда окно нарушает условие.

Нужно ли убирать перевод строки в конце файла?

Да, strip() убирает его, иначе он посчитается символом.

Как проверить решение на маленькой строке?

Напишите медленный перебор всех подстрок и сравните его ответ с ответом быстрого решения на десятке коротких случайных строк.

Задание 24 ЕГЭ по информатике: решайте с автопроверкой

В задании 24 дан файл с одной длинной строкой из букв и цифр. Нужно найти самую длинную подстроку с заданным свойством: без одинаковых соседей, только из разрешённых символов, с ограниченным числом определённых символов.

Решать задачи номера

Как решать программой

Прочитайте строку: s = open("24.txt").read().strip(). Перебор всех подстрок слишком медленный для строки из миллиона символов, поэтому решение идёт одним проходом.

Для свойства «без одинаковых соседей» держите длину текущего участка: если символ совпал с предыдущим, участок начинается заново, иначе становится на один длиннее. Ответ — это наибольшая длина за проход.

Для условий вроде «не больше k символов A» используйте два указателя: правый расширяет окно, левый сдвигается, пока условие нарушено. Каждый символ входит в окно и выходит из него один раз, так что проход линейный.

Для условия «ровно k вхождений сочетания» запишите позиции всех вхождений в список. Самая длинная подходящая подстрока охватывает k вхождений, идущих подряд, и тянется почти до соседних вхождений слева и справа, не захватывая их целиком.

Разбор примера

Строка AAB1B22C. Найдём длину самой длинной подстроки, где соседние символы различны.

s = 'AAB1B22C'
best = cur = 1
for prev, ch in zip(s, s[1:]):
    cur = 1 if ch == prev else cur + 1
    best = max(best, cur)
print(best)

Программа печатает

В строке AAB1B22C самый длинный участок без одинаковых соседей — это AB1B2, пять символов. Участок обрывается перед второй двойкой, а после неё начинается новый: 2C.

Решить эту задачу

Задачи к заданию 24

Участок без одинаковых соседейСредняяРешать
Самый длинный участок из разрешённых буквСредняяРешать
Не больше k отметок об ошибкеСредняяРешать
Ровно k вхождений сочетанияСложнаяРешать
Буквы и цифры по очередиСредняяРешать
Какая буква чаще идёт после сочетанияСредняяРешать
Обрывок бесконечного повтора шаблонаСредняяРешать
Двух букв поровнуСредняяРешать
Самое длинное чётное шестнадцатеричное числоСредняяРешать
Подстрока с суммой цифр не больше порогаСредняяРешать
Кратчайший участок с k нужными буквамиСредняяРешать
Самое длинное правильное выражениеСложнаяРешать
Каждый символ не больше k разСредняяРешать

Бесплатно и без регистрации: пишете код в браузере и проверяете его тестами (без аккаунта — несколько задач в день).

Вопросы и ответы

Почему не перебрать все подстроки?: Для строки из миллиона символов подстрок около 5·10¹¹, программа не успеет. Один проход занимает доли секунды.
Что такое метод двух указателей?: Окно между двумя индексами: правый идёт вперёд, левый догоняет его, когда окно нарушает условие.
Нужно ли убирать перевод строки в конце файла?: Да, strip() убирает его, иначе он посчитается символом.
Как проверить решение на маленькой строке?: Напишите медленный перебор всех подстрок и сравните его ответ с ответом быстрого решения на десятке коротких случайных строк.