Задание 24 ЕГЭ по информатике: самый длинный фрагмент с ровно 20 A

Отработайте точное ограничение окна в строке. Файл с буквами, проверка целого ответа и алгоритм двух указателей.

Следующая задача в кабинете

Проверьте ответ здесь. Появится кнопка к другим заданиям этого номера.

К упражнениям
Скачать 24-rovno-a.txt

В строке BAXAB для ровно двух A подходит вся строка длиной 5.

Задания

1Авторская задача

Файл содержит одну строку из прописных латинских букв. Среди её непрерывных фрагментов, содержащих ровно 20 букв A, найдите длину самого длинного. Символ конца строки не учитывается.

Решение

Пока букв A больше 20, сдвигаем начало окна вправо. При ровно 20 учитываем длину. Правый указатель проходит всю строку, левый движется только вправо, поэтому время O(n).

from pathlib import Path
s = Path("24-rovno-a.txt").read_text().strip()
left = count = best = 0
for right, c in enumerate(s):
    count += c == "A"
    while count > 20:
        count -= s[left] == "A"
        left += 1
    if count == 20:
        best = max(best, right - left + 1)
print(best)

Дальше по теме

Источники