Модуль: Скользящее окно и два указателя

Разбор

Анализ условия

• «ровно по одному разу» → нужно ровно 1 X и ровно 1 Y
• «максимальное» → для каждой допустимой комбинации ищем максимальное расширение

Идея решения

Для каждой позиции right отслеживаем две последние позиции каждой буквы:

last_x, second_last_x — две последние позиции X
last_y, second_last_y — две последние позиции Y

Формула для границ

Чтобы в подстроке [left, right] было ровно 1 X и ровно 1 Y:

left > second_last_x   (исключить предпоследний X)
left > second_last_y   (исключить предпоследний Y)
left ≤ last_x          (включить последний X)
left ≤ last_y          (включить последний Y)

Объединяем:
  min_left = max(second_last_x, second_last_y) + 1
  max_left = min(last_x, last_y)

Если min_left ≤ max_left → подстрока существует
Для максимальной длины берём: left = min_left

Визуализация на примере

Строка: A  B  X  C  Y  D  X  E  Y  F
        0  1  2  3  4  5  6  7  8  9

right = 4 (первая Y)

        A  B  X  C  Y  D  X  E  Y  F
        0  1  2  3  4
              ↑     ↑
           last_x last_y

second_last_x = -1 (не было другого X)
last_x = 2
second_last_y = -1 (не было другого Y)
last_y = 4

min_left = max(-1, -1) + 1 = 0
max_left = min(2, 4) = 2

0 ≤ 2 ✓ → left = 0

Подстрока: s[0:5] = "ABXCY"
Длина = 4 - 0 + 1 = 5

right = 6 (второй X)

        A  B  X  C  Y  D  X  E  Y  F
        0  1  2  3  4  5  6
              ↑     ↑     ↑
           2nd_x last_y last_x

second_last_x = 2
last_x = 6
second_last_y = -1
last_y = 4

min_left = max(2, -1) + 1 = 3
max_left = min(6, 4) = 4

3 ≤ 4 ✓ → left = 3

Подстрока: s[3:7] = "CYDX"
Длина = 6 - 3 + 1 = 4

right = 8 (вторая Y)

        A  B  X  C  Y  D  X  E  Y  F
        0  1  2  3  4  5  6  7  8
              ↑     ↑     ↑     ↑
           2nd_x 2nd_y last_x last_y

second_last_x = 2
last_x = 6
second_last_y = 4
last_y = 8

min_left = max(2, 4) + 1 = 5
max_left = min(6, 8) = 6

5 ≤ 6 ✓ → left = 5

Подстрока: s[5:9] = "DXEY"
Длина = 8 - 5 + 1 = 4

right = 9 (символ F)

Позиции X и Y не изменились

min_left = 5
max_left = 6

left = 5

Подстрока: s[5:10] = "DXEYF"
Длина = 9 - 5 + 1 = 5

Максимум в примере: 5

Код решения

with open("24-280.txt") as f:
    s = f.read()

max_len = 0

# Позиции двух последних X и Y
# -1 означает "ещё не встречался"
last_x = -1
second_last_x = -1
last_y = -1
second_last_y = -1

for right in range(len(s)):
    # Обновляем позиции
    if s[right] == ''X'':
        second_last_x = last_x
        last_x = right
    elif s[right] == ''Y'':
        second_last_y = last_y
        last_y = right

    # Проверяем, есть ли хотя бы 1 X и 1 Y
    if last_x >= 0 and last_y >= 0:
        # Минимальный left: после обоих предпоследних
        min_left = max(second_last_x, second_last_y) + 1
        # Максимальный left: не позже обоих последних
        max_left = min(last_x, last_y)

        if min_left <= max_left:
            length = right - min_left + 1
            max_len = max(max_len, length)

print(max_len)

Сложность

• Время: O(n) — один проход по строке
• Память: O(1) — храним только 4 переменные

Ответ: 193

Обсуждения (0)

Решения (0)

Решения: