24. Подсчет символов: Текстовый файл состоит из заглавных букв латинского алфавита A, B, C, D, E и…
Текстовый файл состоит из заглавных букв латинского алфавита $A$, $B$, $C$, $D$, $E$ и $F$. Определите максимальное количество идущих подряд символов в прилагаемом файле, среди которых пара символов $CD$ (в указанном порядке) встречается не более $140$ раз.
Для выполнения этого задания следует написать программу.
Соберём позиции всех вхождений пары $CD$ — это индексы, где стоит $C$, а следом $D$. Пара считается попавшей в окно, только если внутри оба её символа: начало не левее $L$ и не правее $R-1$.
Формулировка «не более» означает потолок, но брать меньше $140$ вхождений невыгодно — окно от этого только сузится. Поэтому рассуждаем так же, как в случае «ровно». Пусть в окно попали вхождения с номерами от $i$ до $i+139$. Тогда вхождение с номером $i-1$ внутрь попасть не должно, значит левую границу опускаем максимум до $occ[i-1]+1$. А вхождение с номером $i+140$ не должно поместиться целиком, значит правую границу тянем до $occ[i+140]$: сама буква $C$ этой пары в окно попасть может, лишь бы не попала её $D$.
Разница с вариантом «ровно» только в крайнем случае: если всего вхождений не больше $140$, ответом будет вся длина файла. Здесь их $306421$, так что эта ветка не понадобилась.
s = open('24-19.txt').read().strip()
n = len(s)
K = 140
occ = [i for i in range(n-1) if s[i] == 'C' and s[i+1] == 'D']
m = len(occ)
if m <= K:
print(n)
else:
best = 0
for i in range(m - K + 1): # occ[i..i+K-1] — вхождения внутри окна
L = occ[i-1] + 1 if i > 0 else 0 # предыдущее вхождение отсекаем
R = occ[i+K] if i + K < m else n-1 # следующее не должно влезть целиком
best = max(best, R - L + 1)
print(best) # 6413
Проверка найденного окна: длина $6413$, вхождений $CD$ ровно $140$. Слева от окна стоит $C$, а первый символ окна — $D$, то есть шаг влево добавил бы $141$-е вхождение. Справа стоит $D$, а последний символ окна — $C$, шаг вправо тоже добавил бы вхождение. Растянуть некуда.
Метод двух указателей на том же файле даёт то же самое число.