24. Подсчет символов: Текстовый файл состоит из заглавных букв латинского алфавита A, B, C, D, E и…
Текстовый файл состоит из заглавных букв латинского алфавита $A$, $B$, $C$, $D$, $E$ и $F$. Определите минимальное количество идущих подряд символов в прилагаемом файле, среди которых пара символов $AB$ (в указанном порядке) встречается ровно $220$ раз.
Для выполнения этого задания следует написать программу.
Здесь ищется минимум, и это заметно упрощает задачу по сравнению с максимумом. Соберём позиции всех вхождений пары $AB$ — индексы, где стоит $A$, а следом $B$.
Пусть в окно попали вхождения с номерами от $i$ до $i+219$, то есть ровно $220$ штук. Сжимаем окно с обеих сторон до упора. Слева упираемся в самое первое из них: левая граница равна $occ[i]$, дальше двигаться нельзя, потеряем вхождение. Справа упираемся в последнее: правая граница равна $occ[i+219]+1$, потому что в окно должна войти и вторая буква пары, то есть $B$.
Никаких дополнительных проверок не нужно. Окно начинается с $A$ и кончается на $B$, значит соседние вхождения с номерами $i-1$ и $i+220$ внутрь заведомо не попадают — мы взяли ровно минимальный отрезок, накрывающий нужные $220$ пар.
s = open('24-20.txt').read().strip()
n = len(s)
K = 220
occ = [i for i in range(n-1) if s[i] == 'A' and s[i+1] == 'B']
m = len(occ)
best = float('inf')
for i in range(m - K + 1): # occ[i..i+K-1] — вхождения внутри окна
L = occ[i] # начинаем прямо с первого вхождения
R = occ[i+K-1] + 1 # кончаем на второй букве последнего
best = min(best, R - L + 1)
print(best) # 1088
Проверка найденного окна: длина $1088$, вхождений $AB$ ровно $220$, начинается оно с $AB$ и кончается на $AB$. Сжать сильнее нельзя — любой шаг внутрь разрушит крайнюю пару.
Обратите внимание на разницу с задачами на максимум. Там границы упирались в соседние лишние вхождения и требовался сдвиг на единицу ($occ[i-1]+1$ слева и $occ[i+K]$ справа). Здесь всё наоборот: границы упираются в свои же крайние вхождения. Единственное, о чём легко забыть, — прибавить $1$ к правой границе, чтобы захватить букву $B$ последней пары.