24. Подсчет символов: все задания

Условие «начинается с $G$ и внутри больше нет $G$» означает, что строка сама собой разбивается буквами $G$ на независимые отрезки. Каждый кандидат — это буква $G$ плюс текст до следующей $G$. Поэтому достаточно перебрать эти отрезки, а не все подстроки.

Внутри одного отрезка нам нужно ровно $45$ нечётных цифр, значит берём префикс, обрывающийся прямо перед $46$-й нечётной цифрой (а если их в отрезке всего $45$ — берём отрезок целиком). Это и есть максимальная длина для данного отрезка: любой символ дальше — либо $46$-я нечётная цифра, либо уже следующая $G$.

Сама буква $G$ нечётной цифрой не является и в счётчик не идёт, но в длину входит.

s = open('24-01.txt').read().strip()
odd = set('13579')
best = 0

for block in s.split('G')[1:]:      # каждый отрезок — текст после очередной G
    pos = [k for k, c in enumerate(block) if c in odd]
    if len(pos) >= 45:
        # обрываемся перед 46-й нечётной цифрой, либо берём отрезок целиком
        L = 1 + (pos[45] if len(pos) > 45 else len(block))   # +1 — сама буква G
        best = max(best, L)

print(best)   # 76

Проверка найденного фрагмента: длина $76$, первый символ $G$, вхождений $G$ внутри ровно $1$, нечётных цифр ровно $45$, а следующий за фрагментом символ — $9$, то есть удлинить нельзя.

Здесь два условия разного типа: «не менее $110$» — монотонное (от расширения окна только улучшается), а «ровно $90$» — нет. Поэтому опираемся на второе: любое подходящее окно содержит ровно $90$ подряд идущих букв $W$, то есть отрезок $W$ с номерами от $i$ до $i+89$. Значит левая граница лежит между предыдущей буквой $W$ и $w[i]$, а правая — между $w[i+89]$ и следующей буквой $W$. Перебираем $i$, и внутри каждого такого «коридора» ищем самое короткое окно, где вхождений $2025$ набирается $110$.

Внутри коридора левую границу выгодно брать как можно правее, а правую — как можно левее. Двигаем $L$ по позициям вхождений $2025$ в его допустимом диапазоне: чем левее $L$, тем раньше начинается блок из $110$ вхождений и тем меньше можно взять $R$. Для каждого $L$ правая граница равна максимуму из конца $110$-го вхождения и позиции $w[i+89]$ — обе границы обязаны выполняться одновременно.

Подстрока $2025$ сама с собой не пересекается, поэтому вхождения можно просто собрать в список позиций через $find$.

import bisect

s = open('24-02.txt').read().strip()
n = len(s)

occ = []                                   # позиции начал подстроки 2025
p = s.find('2025')
while p != -1:
    occ.append(p)
    p = s.find('2025', p + 1)

w = [i for i, ch in enumerate(s) if ch == 'W']
m, K = len(w), len(occ)
best = float('inf')

for i in range(m - 89):                    # окно содержит W с номерами i..i+89
    loL = w[i-1] + 1 if i > 0 else 0       # левее нельзя: захватим 91-ю W
    hiL = w[i]
    loR = w[i+89]
    hiR = w[i+90] - 1 if i + 90 < m else n - 1

    kw = bisect.bisect_left(occ, hiL)
    kmin = bisect.bisect_left(occ, loL)
    for k in range(kw, kmin - 1, -1):      # k — номер первого вхождения в окне
        if k + 109 >= K:
            continue
        L = min(hiL, occ[k]) if k < K else hiL
        if L < loL:
            break
        R = max(occ[k+109] + 3, loR)       # +3 — последний символ 110-го вхождения
        if R <= hiR:
            best = min(best, R - L + 1)

print(best)   # 780

Проверка найденного окна: длина $780$, букв $W$ ровно $90$, вхождений $2025$ ровно $110$.

Условие «начинается с $N$ и внутри больше нет $N$» означает, что строка сама собой разбивается буквами $N$ на независимые отрезки. Каждый кандидат — это буква $N$ плюс текст до следующей $N$. Поэтому достаточно перебрать эти отрезки, а не все подстроки.

Внутри одного отрезка нам нужно ровно $55$ цифр, значит берём префикс, обрывающийся прямо перед $56$-й цифрой (а если цифр в отрезке всего $55$ — берём отрезок целиком). Это и есть максимальная длина для данного отрезка: любой символ дальше — либо $56$-я цифра, либо уже следующая $N$.

Сама буква $N$ цифрой не является и в счётчик не идёт, но в длину входит.

s = open('24-03.txt').read().strip()
best = 0

for block in s.split('N')[1:]:      # каждый отрезок — текст после очередной N
    pos = [k for k, c in enumerate(block) if c.isdigit()]
    if len(pos) >= 55:
        # обрываемся перед 56-й цифрой, либо берём отрезок целиком
        L = 1 + (pos[55] if len(pos) > 55 else len(block))   # +1 — сама буква N
        best = max(best, L)

print(best)   # 132

Проверка найденного фрагмента: длина $132$, первый символ $N$, вхождений $N$ внутри ровно $1$, цифр ровно $55$, а следующий за фрагментом символ — $3$, то есть удлинить нельзя.

Ключевое упрощение даёт условие «оканчивается подстрокой $2025$»: правая граница окна не произвольна, это конец какого-то вхождения $2025$. Перебираем вхождения: пусть $j$-е вхождение последнее в окне, тогда правая граница $R = occ[j] + 3$.

Дальше работает условие «ровно $50$ раз». Раз последнее вхождение имеет номер $j$, то первое обязано иметь номер $j-49$. Значит вхождение с номером $j-50$ в окно попасть не должно, и левая граница может опуститься максимум до $L = occ[j-50] + 1$. Так мы берём самое длинное окно для данного $j$.

Условие на букву $Y$ — «не менее $140$», оно монотонно: при расширении окна букв $Y$ только прибавляется. Поэтому проверять его достаточно один раз, уже на максимально растянутом окне: если и там $Y$ меньше $140$, то никакое более короткое окно с тем же $j$ не подойдёт.

Подстрока $2025$ сама с собой не пересекается, поэтому позиции вхождений просто собираются через find.

s = open('24-04.txt').read().strip()

occ = []                                   # позиции начал подстроки 2025
p = s.find('2025')
while p != -1:
    occ.append(p)
    p = s.find('2025', p + 1)

py = [0] * (len(s) + 1)                    # префиксные суммы по буквам Y
for i, c in enumerate(s):
    py[i+1] = py[i] + (c == 'Y')

best = 0
for j in range(49, len(occ)):              # j-е вхождение — последнее в окне
    R = occ[j] + 3                         # +3 — окно кончается на 2025
    L = occ[j-50] + 1 if j >= 50 else 0    # не пускаем внутрь 51-е вхождение
    if py[R+1] - py[L] >= 140:
        best = max(best, R - L + 1)

print(best)   # 938

Проверка найденного окна: длина $938$, последние четыре символа — $2025$, вхождений $2025$ ровно $50$, букв $Y$ — $237$, то есть не менее $140$.

Разбираем условие на три независимых требования к искомой подстроке.

Во-первых, это должна быть запись числа в системе с основанием $14$, значит все символы обязаны принадлежать алфавиту $0$–$9$, $A$, $B$, $C$, $D$. Любая буква от $E$ до $Z$ — разделитель. Поэтому строка распадается на блоки допустимых символов, и искать надо внутри блоков.

Во-вторых, число чётное. Основание $14$ чётно, поэтому все разряды, кроме последнего, дают чётный вклад, и чётность числа определяется только последней цифрой. Чётные цифры алфавита: $0$, $2$, $4$, $6$, $8$, $A$ (это $10$) и $C$ (это $12$). Значит подстрока обязана заканчиваться на одну из них.

В-третьих, слова «значащих цифр» означают запрет ведущего нуля, то есть первый символ подстроки не может быть $0$.

Число тем больше, чем больше в нём разрядов, поэтому сначала максимизируем длину. Внутри блока самое левое допустимое начало — первая ненулевая цифра, самый правый допустимый конец — последняя чётная цифра. Их разность и даёт максимальную длину для этого блока. Если длины у нескольких блоков совпали, сравниваем сами записи как строки — при равной длине это и есть сравнение по величине.

import re

s = open('24-05.txt').read().strip()
even = set('02468AC')            # чётные цифры 14-ричной системы

best_len, best_val = 0, ''
for m in re.finditer(r'[0-9A-D]+', s):     # блоки из допустимых символов
    b = m.group()

    i = 0                                  # первая ненулевая цифра
    while i < len(b) and b[i] == '0':
        i += 1
    if i == len(b):
        continue

    j = len(b) - 1                         # последняя чётная цифра
    while j >= i and b[j] not in even:
        j -= 1
    if j < i:
        continue

    cand = b[i:j+1]
    if len(cand) > best_len or (len(cand) == best_len and cand > best_val):
        best_len, best_val = len(cand), cand

print(best_len)   # 2598

Проверка: самый длинный блок допустимых символов имеет длину $2600$, после отсечения ведущих нулей слева и «нечётного хвоста» справа от него остаётся $2598$ символов. Ближайший конкурент даёт лишь $1216$, так что тай-брейк по значению здесь не понадобился.

Условий два, и они ведут себя по-разному. «Ровно $80$ букв $Y$» — жёсткое, оно и ограничивает окно. «Не менее $90$ вхождений $2025$» — монотонное: при расширении окна вхождений только прибавляется, поэтому оно нам не мешает растягиваться.

Раз букв $Y$ ровно $80$, окно содержит какой-то отрезок из $80$ подряд идущих $Y$: с номерами от $i$ до $i+79$. Перебираем $i$. Влево окно можно тянуть до предыдущей буквы $Y$ (не включая её), вправо — до следующей буквы $Y$ (не включая). Это и даёт максимальное окно для данного $i$: ещё один шаг в любую сторону захватит $81$-ю букву $Y$.

Осталось проверить вхождения $2025$. Поскольку окно уже растянуто до предела, если здесь их меньше $90$, то при этом $i$ вариантов нет вовсе. Считать удобно по списку позиций вхождений: нужны те, что начинаются не левее $L$ и целиком помещаются до $R$, то есть начало не правее $R-3$.

import bisect

s = open('24-06.txt').read().strip()
n = len(s)

y = [i for i, c in enumerate(s) if c == 'Y']
starts = []                                # позиции начал подстроки 2025
p = s.find('2025')
while p != -1:
    starts.append(p)
    p = s.find('2025', p + 1)

m = len(y)
best = 0
for i in range(m - 79):                    # окно содержит Y с номерами i..i+79
    L = y[i-1] + 1 if i > 0 else 0         # упираемся в предыдущую Y
    R = y[i+80] - 1 if i + 80 < m else n-1 # упираемся в следующую Y

    lo = bisect.bisect_left(starts, L)
    hi = bisect.bisect_right(starts, R - 3)  # вхождение должно влезть целиком
    if hi - lo >= 90:
        best = max(best, R - L + 1)

print(best)   # 2981

Проверка найденного окна: длина $2981$, букв $Y$ ровно $80$, вхождений $2025$ — $656$, то есть не менее $90$. Слева и справа от окна стоят буквы $Y$ — расширить нельзя.

Условие «начинается чётной цифрой и других чётных цифр внутри нет» устроено так же, как обычное «начинается с буквы $X$ и других $X$ нет». Роль разделителя играет весь набор $0$, $2$, $4$, $6$, $8$. Строка распадается чётными цифрами на независимые отрезки: каждый кандидат — это одна чётная цифра плюс текст до следующей чётной цифры. Перебираем только такие отрезки, а не все подстроки.

Внутри отрезка нужно ровно $30$ букв $W$, значит берём префикс, обрывающийся прямо перед $31$-й буквой $W$ (а если их в отрезке всего $30$ — берём отрезок целиком). Это максимум для данного отрезка: любой символ дальше — либо $31$-я буква $W$, либо уже следующая чётная цифра.

Сама стартовая цифра буквой $W$ не является и в счётчик не идёт, но в длину входит.

import re

s = open('24-07.txt').read().strip()
best = 0

# отрезок = чётная цифра + всё до следующей чётной цифры
for m in re.finditer(r'[02468][^02468]*', s):
    b = m.group()
    pos = [k for k, c in enumerate(b) if c == 'W']
    if len(pos) >= 30:
        # обрываемся перед 31-й W, либо берём отрезок целиком
        best = max(best, pos[30] if len(pos) > 30 else len(b))

print(best)   # 109

Проверка найденного фрагмента: длина $109$, первый символ — цифра $8$, других чётных цифр внутри нет, букв $W$ ровно $30$, а следующий за фрагментом символ — $W$, то есть удлинить нельзя.

Сначала формализуем, что такое корректное выражение. Это число, за которым идёт любое количество пар «знак операции плюс число». Число — это либо одиночный $0$, либо цифра из $6$–$9$, за которой идут любые цифры набора $0$, $6$, $7$, $8$, $9$. Условие про ведущие нули означает ровно одно: с нуля может начинаться только само число $0$.

Ключевой момент, на котором чаще всего ошибаются: искомый фрагмент — это подстрока, поэтому он имеет право начаться в середине блока цифр. Например, в куске $00789$ подстрока $789$ — корректное число. Но такой «обрезанный» старт нельзя продолжить влево знаком операции, потому что слева от него стоит цифра. Значит присоединять к выражению что-то слева можно только тогда, когда число начинается с самого начала своего блока цифр.

Решаем динамикой. Идём слева направо и для каждой позиции $j$ с цифрой считаем $L[j]$ — длину самого длинного корректного выражения, заканчивающегося в этой позиции. Есть два варианта: либо выражение состоит из одного числа, либо к числу слева через знак операции приклеивается уже посчитанное выражение, которое кончалось на два символа левее начала числа.

s = open('24-08.txt').read().strip()
n = len(s)
ops = set('-*')

L = [0] * n          # L[j] — длина макс. верного выражения, кончающегося в j
best = 0
r = 0                # начало текущего блока цифр

for j in range(n):
    if s[j] in ops:
        r = j + 1
        continue

    # 1) выражение из одного числа
    if s[r] != '0':                     # блок начинается со значащей цифры
        cur = j - r + 1
        chain_start = r
    elif j == r:                        # само число 0
        cur = 1
        chain_start = r
    else:                               # блок начался с 0 — стартуем с первой ненулевой
        q = r
        while q <= j and s[q] == '0':
            q += 1
        cur = j - q + 1 if q <= j else 1
        chain_start = -1                # слева цифра, знак операции не приписать

    # 2) приклеиваем слева выражение через знак операции
    if chain_start >= 2 and s[chain_start-1] in ops and L[chain_start-2] > 0:
        cur = max(cur, L[chain_start-2] + 1 + (j - chain_start + 1))

    L[j] = cur
    best = max(best, cur)

print(best)   # 154

Проверка найденного фрагмента: длина $154$, он целиком распознаётся регулярным выражением для корректной записи, а слева и справа от него стоят знаки $*$, то есть расширить его нельзя.

Задача та же, что и предыдущая, меняется только набор цифр. Корректное выражение — это число, за которым идёт любое количество пар «знак операции плюс число». Число — либо одиночный $0$, либо цифра из $1$–$4$, за которой идут любые цифры набора $0$–$4$. Запрет ведущих нулей означает ровно одно: с нуля может начинаться только само число $0$.

Главная тонкость — искомый фрагмент это подстрока, поэтому он может начаться в середине блока цифр. В куске $00341$ подстрока $341$ уже корректное число. Но такой «обрезанный» старт нельзя продолжить влево знаком операции: слева от него стоит цифра. Присоединять что-то слева можно только когда число начинается с самого начала своего блока цифр.

Идём слева направо и для каждой позиции $j$ с цифрой считаем $L[j]$ — длину самого длинного корректного выражения, кончающегося в этой позиции. Вариантов два: либо это одно число, либо к числу слева через знак операции приклеивается уже посчитанное выражение, которое кончалось на два символа левее начала числа.

s = open('24-09.txt').read().strip()
n = len(s)
ops = set('-*')

L = [0] * n          # L[j] — длина макс. верного выражения, кончающегося в j
best = 0
r = 0                # начало текущего блока цифр

for j in range(n):
    if s[j] in ops:
        r = j + 1
        continue

    # 1) выражение из одного числа
    if s[r] != '0':                     # блок начинается со значащей цифры
        cur = j - r + 1
        chain = r
    elif j == r:                        # само число 0
        cur = 1
        chain = r
    else:                               # блок начался с 0 — стартуем с первой ненулевой
        q = r
        while q <= j and s[q] == '0':
            q += 1
        cur = j - q + 1 if q <= j else 1
        chain = -1                      # слева цифра, знак операции не приписать

    # 2) приклеиваем слева выражение через знак операции
    if chain >= 2 and s[chain-1] in ops and L[chain-2] > 0:
        cur = max(cur, L[chain-2] + 1 + (j - chain + 1))

    L[j] = cur
    best = max(best, cur)

print(best)   # 933

Проверка найденного фрагмента: длина $933$, он целиком распознаётся регулярным выражением для корректной записи. Окружение — $33*$ слева и $33**$ справа. Влево не растянуть: перед знаком $*$ стоит ещё один знак $-$, два знака подряд запрещены. Вправо тоже: фрагмент кончается числом $0$, а следующий символ — цифра $3$, и $03$ было бы числом с ведущим нулём.

Корректное выражение — это число, за которым идёт любое количество пар «знак операции плюс число». Число — либо одиночный $0$, либо цифра из $5$–$7$, за которой идут любые цифры набора $0$, $5$, $6$, $7$. Запрет ведущих нулей означает ровно одно: с нуля может начинаться только само число $0$.

Тонкость, которая в этом файле по-настоящему сработала: искомый фрагмент — подстрока, поэтому он может начаться в середине блока цифр. Здесь ответ как раз такой. Фрагмент стартует внутри блока $05006\ldots$, отбрасывая ведущий ноль, и начинается с цифры $5$. Если ограничиться стартами только сразу после знака операции, получится $197$ — заметно меньше правильного ответа.

Но у такого «обрезанного» старта есть плата: продолжить его влево знаком операции уже нельзя, потому что слева стоит цифра. Присоединять что-то слева можно только когда число начинается с самого начала своего блока цифр. Это и отражено в переменной chain.

Идём слева направо и для каждой позиции $j$ с цифрой считаем $L[j]$ — длину самого длинного корректного выражения, кончающегося в этой позиции. Вариантов два: либо это одно число, либо к числу слева через знак операции приклеивается уже посчитанное выражение, кончавшееся на два символа левее начала числа.

s = open('24-10.txt').read().strip()
n = len(s)
ops = set('-*')

L = [0] * n          # L[j] — длина макс. верного выражения, кончающегося в j
best = 0
r = 0                # начало текущего блока цифр

for j in range(n):
    if s[j] in ops:
        r = j + 1
        continue

    # 1) выражение из одного числа
    if s[r] != '0':                     # блок начинается со значащей цифры
        cur = j - r + 1
        chain = r
    elif j == r:                        # само число 0
        cur = 1
        chain = r
    else:                               # блок начался с 0 — стартуем с первой ненулевой
        q = r
        while q <= j and s[q] == '0':
            q += 1
        cur = j - q + 1 if q <= j else 1
        chain = -1                      # слева цифра, знак операции не приписать

    # 2) приклеиваем слева выражение через знак операции
    if chain >= 2 and s[chain-1] in ops and L[chain-2] > 0:
        cur = max(cur, L[chain-2] + 1 + (j - chain + 1))

    L[j] = cur
    best = max(best, cur)

print(best)   # 211

Проверка найденного фрагмента: длина $211$, он целиком распознаётся регулярным выражением для корректной записи. Слева от него $-70$, то есть цифра — расширяться некуда. Справа фрагмент кончается на $7507$, а дальше идёт $-$, два знака подряд, что запрещено.

Здесь условие локальное: оно ограничивает только соседние пары символов. Буква не рядом с буквой и цифра не рядом с цифрой означает ровно одно — типы символов чередуются. Конкретные значения ($Q$, $R$, $W$ или $1$, $2$, $4$) роли не играют, важен лишь признак «цифра или буква».

Раз ограничение накладывается только на пары соседей, никакого окна с двумя указателями не нужно. Достаточно одного прохода: ведём длину текущей чередующейся цепочки. Если очередной символ по типу отличается от предыдущего — цепочка продолжается, если совпадает — она обрывается и начинается заново с длины $1$.

s = open('24-12.txt').read().strip()

best = cur = 1
for i in range(1, len(s)):
    if s[i].isdigit() != s[i-1].isdigit():   # тип сменился — цепочка растёт
        cur += 1
    else:                                    # два подряд одного типа — обрыв
        cur = 1
    best = max(best, cur)

print(best)   # 17

Обратите внимание на начальное значение cur = 1: одиночный символ сам по себе условию удовлетворяет, нарушать там нечего.

Проверка найденного фрагмента: это $4W2W2R2R4Q4Q4Q2R2$, длина $17$, типы внутри действительно чередуются. Слева от него стоит цифра $1$, а фрагмент начинается с цифры $4$; справа стоит цифра $4$, а фрагмент кончается цифрой $2$. Значит ни влево, ни вправо расшириться нельзя.

Условие «не более $110$» монотонно в другую сторону, чем привычное «не менее»: чем шире окно, тем больше вхождений, значит ограничение работает как потолок и само задаёт границы. Никаких «ровно» здесь нет, поэтому задача решается напрямую.

Соберём позиции всех вхождений пары $AB$ — это индексы, где стоит $A$, а следом $B$. Пара считается попавшей в окно, только если оба её символа внутри: начало не левее $L$ и не правее $R-1$.

Дальше рассуждаем так. Пусть в окно попали вхождения с номерами от $i$ до $i+109$ (ровно $110$ штук — брать меньше невыгодно, окно только сузится). Тогда предыдущее вхождение с номером $i-1$ внутрь попасть не должно, значит левую границу можно опустить максимум до $occ[i-1]+1$. А вхождение с номером $i+110$ не должно поместиться целиком, значит правая граница дотягивается максимум до $occ[i+110]$ — сама буква $A$ этой пары в окно попасть может, лишь бы не попала её $B$.

Отдельно стоит помнить про край: если всего вхождений не больше $110$, ответ — вся длина файла.

s = open('24-11.txt').read().strip()
n = len(s)
K = 110

occ = [i for i in range(n-1) if s[i] == 'A' and s[i+1] == 'B']
m = len(occ)

if m <= K:
    print(n)
else:
    best = 0
    for i in range(m - K + 1):             # occ[i..i+K-1] — вхождения внутри окна
        L = occ[i-1] + 1 if i > 0 else 0   # предыдущее вхождение отсекаем
        R = occ[i+K] if i + K < m else n-1 # 111-е вхождение не должно влезть целиком
        best = max(best, R - L + 1)
    print(best)   # 628

Тот же ответ даёт и классический метод двух указателей: ведём правую границу вперёд, а левую подтягиваем, пока вхождений не станет больше $110$. Он короче в записи, но заметно медленнее на файле в $10$ миллионов символов, зато удобен как независимая проверка.

Соберём позиции всех вхождений пары $BC$ — это индексы, где стоит $B$, а следом $C$. Пара считается попавшей в окно, только если внутри оба её символа: начало не левее $L$ и не правее $R-1$.

Пусть в окно попали вхождения с номерами от $i$ до $i+189$, то есть ровно $190$ штук. Тогда вхождение с номером $i-1$ внутрь попасть не должно, значит левую границу опускаем максимум до $occ[i-1]+1$. А вхождение с номером $i+190$ не должно поместиться целиком, значит правую границу тянем до $occ[i+190]$: сама буква $B$ этой пары в окно попасть может, лишь бы не попала её $C$.

s = open('24-13.txt').read().strip()
n = len(s)
K = 190

occ = [i for i in range(n-1) if s[i] == 'B' and s[i+1] == 'C']
m = len(occ)

best = 0
for i in range(m - K + 1):             # occ[i..i+K-1] — вхождения внутри окна
    L = occ[i-1] + 1 if i > 0 else 0   # предыдущее вхождение отсекаем
    R = occ[i+K] if i + K < m else n-1 # следующее не должно влезть целиком
    best = max(best, R - L + 1)

print(best)   # 2287

Проверка найденного окна: длина $2287$, вхождений $BC$ ровно $190$. Слева от окна стоит $B$, а первый символ окна — $C$, то есть шаг влево добавил бы $191$-е вхождение. Справа от окна стоит $C$, а последний символ окна — $B$, то есть шаг вправо тоже добавил бы вхождение. Растянуть некуда.

Тот же ответ даёт метод двух указателей: ведём правую границу вперёд, подтягиваем левую, пока вхождений больше $190$, и запоминаем длину в моменты, когда их ровно $190$. На файле в $10$ миллионов символов он заметно медленнее, но удобен как независимая проверка.

Соберём позиции всех вхождений пары $CD$ — это индексы, где стоит $C$, а следом $D$. Пара считается попавшей в окно, только если внутри оба её символа: начало не левее $L$ и не правее $R-1$.

Пусть в окно попали вхождения с номерами от $i$ до $i+159$, то есть ровно $160$ штук. Тогда вхождение с номером $i-1$ внутрь попасть не должно, значит левую границу опускаем максимум до $occ[i-1]+1$. А вхождение с номером $i+160$ не должно поместиться целиком, значит правую границу тянем до $occ[i+160]$: сама буква $C$ этой пары в окно попасть может, лишь бы не попала её $D$.

s = open('24-14.txt').read().strip()
n = len(s)
K = 160

occ = [i for i in range(n-1) if s[i] == 'C' and s[i+1] == 'D']
m = len(occ)

best = 0
for i in range(m - K + 1):             # occ[i..i+K-1] — вхождения внутри окна
    L = occ[i-1] + 1 if i > 0 else 0   # предыдущее вхождение отсекаем
    R = occ[i+K] if i + K < m else n-1 # следующее не должно влезть целиком
    best = max(best, R - L + 1)

print(best)   # 9712

Проверка найденного окна: длина $9712$, вхождений $CD$ ровно $160$. Слева от окна стоит $C$, а первый символ окна — $D$, то есть шаг влево добавил бы $161$-е вхождение. Справа стоит $D$, а последний символ окна — $C$, шаг вправо тоже добавил бы вхождение. Растянуть некуда.

Окно получилось необычно длинным — почти $10$ тысяч символов при $224680$ вхождениях $CD$ во всём файле. Это нормально: в файле есть участок, где буквы $C$ и $D$ почти не встречаются подряд, и именно он даёт максимум. Метод двух указателей на том же файле даёт то же самое число.

Корректное выражение — это число, за которым идёт любое количество пар «знак операции плюс число». Число — либо одиночный $0$, либо цифра из $2$–$5$, за которой идут любые цифры набора $0$, $2$, $3$, $4$, $5$. Запрет ведущих нулей означает ровно одно: с нуля может начинаться только само число $0$.

Тонкость, которая здесь снова сработала: искомый фрагмент — подстрока, поэтому он может начаться в середине блока цифр. В этом файле ответ именно такой — фрагмент стартует сразу после ведущего нуля, отбрасывая его. Но у обрезанного старта есть плата: продолжить его влево знаком операции нельзя, слева стоит цифра. Присоединять что-то слева можно только когда число начинается с самого начала своего блока цифр. Это и отражает переменная chain.

Идём слева направо и для каждой позиции $j$ с цифрой считаем $L[j]$ — длину самого длинного корректного выражения, кончающегося в этой позиции. Вариантов два: либо это одно число, либо к числу слева через знак операции приклеивается уже посчитанное выражение, кончавшееся на два символа левее начала числа.

s = open('24-15.txt').read().strip()
n = len(s)
ops = set('-*')

L = [0] * n          # L[j] — длина макс. верного выражения, кончающегося в j
best = 0
r = 0                # начало текущего блока цифр

for j in range(n):
    if s[j] in ops:
        r = j + 1
        continue

    # 1) выражение из одного числа
    if s[r] != '0':                     # блок начинается со значащей цифры
        cur = j - r + 1
        chain = r
    elif j == r:                        # само число 0
        cur = 1
        chain = r
    else:                               # блок начался с 0 — стартуем с первой ненулевой
        q = r
        while q <= j and s[q] == '0':
            q += 1
        cur = j - q + 1 if q <= j else 1
        chain = -1                      # слева цифра, знак операции не приписать

    # 2) приклеиваем слева выражение через знак операции
    if chain >= 2 and s[chain-1] in ops and L[chain-2] > 0:
        cur = max(cur, L[chain-2] + 1 + (j - chain + 1))

    L[j] = cur
    best = max(best, cur)

print(best)   # 569

Проверка найденного фрагмента: длина $569$, он целиком распознаётся регулярным выражением для корректной записи. Слева от него $530$, то есть цифра — расширяться некуда. Справа фрагмент кончается на $5200$, а дальше идёт $-$, два знака подряд, что запрещено.

Корректное выражение — это число, за которым идёт любое количество пар «знак операции плюс число». Число — либо одиночный $0$, либо цифра из $4$–$7$, за которой идут любые цифры набора $0$, $4$, $5$, $6$, $7$. Запрет ведущих нулей означает ровно одно: с нуля может начинаться только само число $0$.

Помним про подстроку: фрагмент имеет право начаться в середине блока цифр, отбросив ведущие нули. Но у такого обрезанного старта есть плата — продолжить его влево знаком операции нельзя, слева стоит цифра. Присоединять что-то слева можно только когда число начинается с самого начала своего блока цифр. Это и отражает переменная chain.

Идём слева направо и для каждой позиции $j$ с цифрой считаем $L[j]$ — длину самого длинного корректного выражения, кончающегося в этой позиции. Вариантов два: либо это одно число, либо к числу слева через знак операции приклеивается уже посчитанное выражение, кончавшееся на два символа левее начала числа.

s = open('24-16.txt').read().strip()
n = len(s)
ops = set('-*')

L = [0] * n          # L[j] — длина макс. верного выражения, кончающегося в j
best = 0
r = 0                # начало текущего блока цифр

for j in range(n):
    if s[j] in ops:
        r = j + 1
        continue

    # 1) выражение из одного числа
    if s[r] != '0':                     # блок начинается со значащей цифры
        cur = j - r + 1
        chain = r
    elif j == r:                        # само число 0
        cur = 1
        chain = r
    else:                               # блок начался с 0 — стартуем с первой ненулевой
        q = r
        while q <= j and s[q] == '0':
            q += 1
        cur = j - q + 1 if q <= j else 1
        chain = -1                      # слева цифра, знак операции не приписать

    # 2) приклеиваем слева выражение через знак операции
    if chain >= 2 and s[chain-1] in ops and L[chain-2] > 0:
        cur = max(cur, L[chain-2] + 1 + (j - chain + 1))

    L[j] = cur
    best = max(best, cur)

print(best)   # 206

Проверка найденного фрагмента: длина $206$, он целиком распознаётся регулярным выражением для корректной записи. Слева от него идёт $7***$, то есть перед стартом стоит знак, а перед ним ещё один — влево не растянуть. Справа фрагмент кончается на $6604$, а дальше $-*$, два знака подряд, что тоже запрещено.

Обратите внимание на длину файла: $10000001$ символ, нечётное число. Это лишний повод не забывать про .strip()при чтении — перевод строки в конце легко попадает в подсчёт и портит ответ.

Соберём позиции всех вхождений пары $AB$ — это индексы, где стоит $A$, а следом $B$. Пара считается попавшей в окно, только если внутри оба её символа: начало не левее $L$ и не правее $R-1$.

Пусть в окно попали вхождения с номерами от $i$ до $i+99$, то есть ровно $100$ штук. Тогда вхождение с номером $i-1$ внутрь попасть не должно, значит левую границу опускаем максимум до $occ[i-1]+1$. А вхождение с номером $i+100$ не должно поместиться целиком, значит правую границу тянем до $occ[i+100]$: сама буква $A$ этой пары в окно попасть может, лишь бы не попала её $B$.

s = open('24-17.txt').read().strip()
n = len(s)
K = 100

occ = [i for i in range(n-1) if s[i] == 'A' and s[i+1] == 'B']
m = len(occ)

best = 0
for i in range(m - K + 1):             # occ[i..i+K-1] — вхождения внутри окна
    L = occ[i-1] + 1 if i > 0 else 0   # предыдущее вхождение отсекаем
    R = occ[i+K] if i + K < m else n-1 # следующее не должно влезть целиком
    best = max(best, R - L + 1)

print(best)   # 750

Проверка найденного окна: длина $750$, вхождений $AB$ ровно $100$. Слева от окна стоит $A$, а первый символ окна — $B$, то есть шаг влево добавил бы $101$-е вхождение. Справа стоит $B$, а последний символ окна — $A$, шаг вправо тоже добавил бы вхождение. Растянуть некуда.

Метод двух указателей на том же файле даёт то же самое число.

Корректное выражение — это число, за которым идёт любое количество пар «знак операции плюс число». Число — либо одиночный $0$, либо цифра из $2$–$5$, за которой идут любые цифры набора $0$, $2$, $3$, $4$, $5$. Запрет ведущих нулей означает ровно одно: с нуля может начинаться только само число $0$.

Этот файл устроен иначе, чем предыдущие. Здесь очень много нулей и знаков операций, а длинных блоков цифр почти нет. Найденный фрагмент состоит в основном из цепочек вида $00-00$, где каждое число — одиночный ноль. Это законно: $0$ сам по себе корректное число без ведущих нулей. А вот кусок $00$ уже недопустим, и именно на таких местах цепочки рвутся.

Отсюда видно, зачем в разборе нужна отдельная ветка j == r. Если блок цифр начинается с нуля и состоит из одного символа, это число $0$, и оно начинается с начала блока, значит к нему можно приклеить выражение слева. Если же блок начинается с нуля и тянется дальше, стартовать приходится с первой ненулевой цифры, а такой обрезанный старт влево уже не продолжить — слева стоит цифра.

Идём слева направо и для каждой позиции $j$ с цифрой считаем $L[j]$ — длину самого длинного корректного выражения, кончающегося в этой позиции. Вариантов два: либо это одно число, либо к числу слева через знак операции приклеивается уже посчитанное выражение, кончавшееся на два символа левее начала числа.

s = open('24-18.txt').read().strip()
n = len(s)
ops = set('-*')

L = [0] * n          # L[j] — длина макс. верного выражения, кончающегося в j
best = 0
r = 0                # начало текущего блока цифр

for j in range(n):
    if s[j] in ops:
        r = j + 1
        continue

    # 1) выражение из одного числа
    if s[r] != '0':                     # блок начинается со значащей цифры
        cur = j - r + 1
        chain = r
    elif j == r:                        # само число 0
        cur = 1
        chain = r
    else:                               # блок начался с 0 — стартуем с первой ненулевой
        q = r
        while q <= j and s[q] == '0':
            q += 1
        cur = j - q + 1 if q <= j else 1
        chain = -1                      # слева цифра, знак операции не приписать

    # 2) приклеиваем слева выражение через знак операции
    if chain >= 2 and s[chain-1] in ops and L[chain-2] > 0:
        cur = max(cur, L[chain-2] + 1 + (j - chain + 1))

    L[j] = cur
    best = max(best, cur)

print(best)   # 193

Проверка найденного фрагмента: длина $193$, он начинается с $0-0204024-0000*$ и кончается на $0-0-0-0-000$, целиком распознаётся регулярным выражением для корректной записи. Слева от него $-0*-$, то есть перед стартом знак, а перед ним ещё один — влево не растянуть. Справа идёт $*-$, два знака подряд, что запрещено.

Соберём позиции всех вхождений пары $CD$ — это индексы, где стоит $C$, а следом $D$. Пара считается попавшей в окно, только если внутри оба её символа: начало не левее $L$ и не правее $R-1$.

Формулировка «не более» означает потолок, но брать меньше $140$ вхождений невыгодно — окно от этого только сузится. Поэтому рассуждаем так же, как в случае «ровно». Пусть в окно попали вхождения с номерами от $i$ до $i+139$. Тогда вхождение с номером $i-1$ внутрь попасть не должно, значит левую границу опускаем максимум до $occ[i-1]+1$. А вхождение с номером $i+140$ не должно поместиться целиком, значит правую границу тянем до $occ[i+140]$: сама буква $C$ этой пары в окно попасть может, лишь бы не попала её $D$.

Разница с вариантом «ровно» только в крайнем случае: если всего вхождений не больше $140$, ответом будет вся длина файла. Здесь их $306421$, так что эта ветка не понадобилась.

s = open('24-19.txt').read().strip()
n = len(s)
K = 140

occ = [i for i in range(n-1) if s[i] == 'C' and s[i+1] == 'D']
m = len(occ)

if m <= K:
    print(n)
else:
    best = 0
    for i in range(m - K + 1):             # occ[i..i+K-1] — вхождения внутри окна
        L = occ[i-1] + 1 if i > 0 else 0   # предыдущее вхождение отсекаем
        R = occ[i+K] if i + K < m else n-1 # следующее не должно влезть целиком
        best = max(best, R - L + 1)
    print(best)   # 6413

Проверка найденного окна: длина $6413$, вхождений $CD$ ровно $140$. Слева от окна стоит $C$, а первый символ окна — $D$, то есть шаг влево добавил бы $141$-е вхождение. Справа стоит $D$, а последний символ окна — $C$, шаг вправо тоже добавил бы вхождение. Растянуть некуда.

Метод двух указателей на том же файле даёт то же самое число.

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