Карточки
Тесты
Главная
Курсы
Подписка
24. Подсчет символов: #297623
Текстовый файл содержит только заглавные буквы латинского алфавита ($ABC\ldots Z$). Определите максимальную длину непрерывного фрагмента, который начинается и заканчивается одной и той же буквой из первой половины алфавита (от $A$ до $M$) и не содержит эту букву внутри.
Условие «начинается и заканчивается буквой $c$, а внутри её нет» означает ровно одно: границы фрагмента — это два соседних вхождения буквы $c$. Между ними этой буквы нет по определению соседства. Значит перебирать подстроки не нужно вовсе, достаточно найти максимальный разрыв между соседними вхождениями для каждой из тринадцати букв $A$–$M$.
Делается это одним проходом. Для каждой буквы храним позицию её последнего встреченного вхождения. Встретив букву снова, сразу получаем кандидата длиной $i — last[c] + 1$: плюс один, потому что обе граничные буквы входят в длину. Затем обновляем last[c].
Буквы от $N$ до $Z$ просто игнорируем — они могут стоять внутри фрагмента сколько угодно раз, ограничение на них не распространяется.
s = open('24-23.txt').read().strip()
last = {} # позиция предыдущего вхождения буквы
best = 0
for i, c in enumerate(s):
if 'A' <= c <= 'M':
if c in last:
best = max(best, i - last[c] + 1) # +1 — обе границы входят в длину
last[c] = i
print(best) # 322
Проверка найденного фрагмента: длина $322$, он начинается и кончается буквой $M$, внутри буква $M$ не встречается ни разу.
Обратите внимание на диапазон $A$–$M$: сравнение 'A' <= c <= 'M' работает потому, что буквы идут подряд в таблице символов. Если такая запись кажется рискованной, можно написать явно c in 'ABCDEFGHIJKLM'.
20
