24 задание ЕГЭ информатика

Задание 24 – текстовый файл из одной длинной строки (до миллиона символов). Найти максимальную длину подстроки с условиями: не более/ровно k определённых букв, определённое количество вхождений подстроки, символы чередуются, нет двух одинаковых подряд. 1 балл. Нужна программа с линейным временем.

Метод двух указателей (скользящее окно)

Окно [l; r] расширяется вправо; если условие нарушено – сдвигаем левую границу, пока не восстановится. Так каждое окно с максимальной длиной проверяется за O(n).

s = open("24.txt").readline().strip()
k = 80
best = l = cnt = 0
for r in range(len(s)):
    if s[r] == "Y":
        cnt += 1
    while cnt > k:                 # нарушили «не более k букв Y»
        if s[l] == "Y":
            cnt -= 1
        l += 1
    best = max(best, r - l + 1)
print(best)

«Ровно k» через позиции. Сохрани индексы всех букв Y: pos = [-1] + [i for i, c in enumerate(s) if c == "Y"] + [len(s)]. Окно с ровно k буквами Y от pos[i] до pos[i + k − 1] максимально расширяется до соседних Y: длина = pos[i + k] − pos[i − 1] − 1.

Ещё приёмы

• Самая длинная цепочка без двух одинаковых подряд: счётчик cur, сбрасывающийся при s[i] == s[i − 1].
• Подсчёт вхождений подстроки с перекрытием – цикл по i и s[i:i + 4] == "2025"; s.count() перекрытия не считает.
• Разбиение по символу: s.split("X") – куски без X.

Разобранный пример. s = "AXBXXCXDXEFX", не более 2 букв X. Лучшее окно – "CXDXEF" (длина 6). Программа выводит 6.

Ловушки: перебор всех подстрок O(n²) на миллионе символов не уложится во время; забытый .strip() добавляет символ перевода строки; условия «ровно» и «не менее» требуют разных схем.