Подготовка к школе
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
Для всех
Назад

24. Подсчет символов: #297622

Сообщить о проблеме
Задание #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$-е вхождение соответствующей буквы. Растянуть некуда.

Файл здесь маленький, чуть больше миллиона символов, поэтому двух указателей вполне достаточно по времени.

Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение