Задание EGEINF199381: Обработка текстового файла

Решение.
В приложенном файле 10000000 символов данных. Рассматриваем непрерывные фрагменты строки; символы нельзя переставлять или пропускать. Сохраним приложенный текстовый файл под именем data.txt. Конечный перевод строки удаляем, остальные символы сохраняем.
Выпишем в возрастающем порядке позиции начала всех вхождений AB. Обозначим этот список pos. Индексы в программе начинаются с нуля. Длина искомого сочетания равна 2.
Любой фрагмент, содержащий 220 вхождений, содержит последовательный блок из 220 элементов списка pos. Поэтому достаточно перебрать начала таких блоков.
Для блока с первым вхождением pos[i] и последним pos[i + 219] кратчайший фрагмент начинается в pos[i] и заканчивается сразу после последнего сочетания. Его длина равна pos[i + 219] − pos[i] + 2.
Удлинение слева или справа не улучшает минимум. Если разрешено больше заданного числа вхождений, лишние крайние вхождения можно удалить и получить не более длинный фрагмент с ровно заданным числом. Поэтому тот же перебор даёт минимум и для требования «не менее».
В данном сочетании нет самоперекрытий, поэтому найденный блок содержит ровно указанное число вхождений; обычный поиск finditer не теряет позиции.
Программа:

import re

with open("data.txt", encoding="utf-8-sig") as f:
    s = f.read().rstrip("\r\n")
from array import array
pos = array("i", (m.start() for m in re.finditer('AB', s)))
k = 220
answer = len(s) + 1
for i in range(len(pos) - k + 1):
    length = pos[i + k - 1] - pos[i] + 2
    answer = min(answer, length)
print(answer)

Проверка результата. Нумеруем символы исходной строки с единицы. Один из оптимальных фрагментов имеет следующие границы:

Разность границ с учётом обоих концов: 6604495 − 6603408 + 1 = 1088.
В найденном фрагменте 220 вхождений AB. Во всём файле их 1598764. Проверены все последовательные блоки нужного размера и крайние границы.
Полный проход по приложенному файлу даёт итоговый ответ. Проверка коротких строк полным перебором всех подстрок подтверждает обработку крайних случаев.
Ответ: 1088.