Задание №24 — Обработка строк, нахождение подстроки

Решение:

В файле записана одна длинная строка из букв T, U, V, W, X, Y, Z (десять миллионов символов). Нужен самый длинный непрерывный кусок этой строки, в котором буква T встречается ровно 100 раз.

Ключевая идея: любой такой кусок содержит ровно сто подряд идущих (по порядку следования в строке) букв T, а между ними и по краям стоят произвольные другие буквы. Значит, достаточно перебрать все окна из 100 подряд идущих букв T и для каждого окна раздвинуть границы максимально широко — влево до предыдущей буквы T (не захватывая её) и вправо до следующей буквы T (тоже не захватывая её). Если слева или справа буквы T больше нет, границей служит начало или конец строки. Из всех полученных длин берём наибольшую.

Для этого сначала выпишем в список номера позиций всех букв T, а затем пройдёмся по нему окном ширины 100.

s = open('24.txt').read().strip()
p = [i for i in range(len(s)) if s[i] == 'T']

best = 0
for k in range(len(p) - 99):
    # окно из ста букв T: p[k] … p[k+99]
    left = p[k - 1] + 1 if k > 0 else 0
    right = p[k + 100] - 1 if k + 100 < len(p) else len(s) - 1
    best = max(best, right - left + 1)

print(best)

Программа работает за один проход по списку позиций, то есть за $O(N)$, и выводит 133. Это означает, что в найденном фрагменте кроме ста букв T стоят ещё 33 буквы других видов. Ответ: 133