Задание 24 ЕГЭ: цепочка с ограничением на число вхождений

Цепочка с ограничением на число вхождений. Тема номера — обработка символьных строк. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Задание выполняется с использованием прилагаемого файла.

Текстовый файл 24.txt содержит строку из 100 000 символов — заглавных латинских букв A, B, C и D.

Определите максимальное количество идущих подряд символов, среди которых буква C встречается не более 50 раз.

Для выполнения этого задания следует написать программу.

Скачать файл к примеру

Решение

«Не более k раз» — свойство всего куска, поэтому нужен не счётчик со сбросом, а скользящее окно. Правый край идёт по строке; когда нужных букв в окне стало больше 50, подтягиваем левый край. Левый край двигается только вперёд, так что это один проход.

Ответ: 361.

s = open("24.txt").read().strip()
k = 50
best = left = cnt = 0
for right, c in enumerate(s):
    if c in "C":
        cnt += 1
    while cnt > k:                # окно нарушено —
        if s[left] in "C":
            cnt -= 1
        left += 1                 # подтягиваем левый край
    best = max(best, right - left + 1)
print(best)

Решить такую задачу — новый вариант с проверкой