24. Подсчет символов: #297622
Текстовый файл содержит только заглавные буквы латинского алфавита ($ABC\ldots Z$). Определите максимальное количество идущих подряд символов, среди которых каждая из букв $UVWXYZ$ встречается не более ста раз.
Ограничение здесь монотонное: при расширении окна количество каждой буквы только растёт, поэтому нарушение никогда не «чинится» само. Это ровно тот случай, когда работает классический метод двух указателей.
Ведём правую границу вперёд по всем символам. Если очередной символ — одна из шести отслеживаемых букв, увеличиваем её счётчик. Как только счётчик превысил $100$, подтягиваем левую границу вправо до тех пор, пока эта буква не вернётся к сотне. Сдвигая левую границу, не забываем уменьшать счётчики уходящих символов. После каждого шага правой границы обновляем ответ.
Важная деталь: условие «каждая из букв не более ста раз» — это шесть независимых ограничений, а не одно на их сумму. Считать надо шесть отдельных счётчиков.
s = open('24-22.txt').read().strip()
n = len(s)
cnt = {c: 0 for c in 'UVWXYZ'}
best = 0
L = 0
for R in range(n):
c = s[R]
if c in cnt:
cnt[c] += 1
while cnt[c] > 100: # сужаем, пока буква c не вернётся к 100
if s[L] in cnt:
cnt[s[L]] -= 1
L += 1
best = max(best, R - L + 1)
print(best) # 2844
Проверка найденного окна: длина $2844$, буква $U$ встречается $92$ раза, $V$ — $91$, а $W$, $X$, $Y$ и $Z$ — ровно по $100$. Слева от окна стоит $Y$, справа $Z$, то есть шаг в любую сторону даёт $101$-е вхождение соответствующей буквы. Растянуть некуда.
Файл здесь маленький, чуть больше миллиона символов, поэтому двух указателей вполне достаточно по времени.