Шаблон 3 — "РОВНО K раз", ищем МАКСИМУМ
Задача-пример
Найти максимальную подстроку, где буква X встречается ровно 2 раза.
Строка: A B X A X X A B
Принцип
Используем позиции целевых символов:
1. Собираем все позиции буквы X 2. Добавляем фиктивные границы: -1 слева и len(s) справа 3. Для каждой пары из K подряд идущих X находим максимальное расширение
Пошаговый разбор
Строка: A B X A X X A B
0 1 2 3 4 5 6 7
Позиции X: [2, 4, 5]
Добавляем границы: [-1, 2, 4, 5, 8]
↑ ↑
фиктивная фиктивная
левая правая
Идея: между positions[i-1] и positions[i+k] находятся ровно K букв X.
positions = [-1, 2, 4, 5, 8]
0 1 2 3 4
Для k=2 перебираем начальные позиции i = 1, 2:
i = 1: берём X на позициях 2 и 4
A B X A X X A B
-1 0 1 2 3 4 5 6 7 8
↑ ↑ ↑ ↑ ↑
p[0] p[1] p[2]p[3] p[4]
X на позициях positions[1]=2 и positions[2]=4
Левая граница: positions[i-1] + 1 = positions[0] + 1 = -1 + 1 = 0
Правая граница: positions[i+k] - 1 = positions[3] - 1 = 5 - 1 = 4
Подстрока [0, 4] = "A B X A X", длина = 5
i = 2: берём X на позициях 4 и 5
X на позициях positions[2]=4 и positions[3]=5
Левая граница: positions[i-1] + 1 = positions[1] + 1 = 2 + 1 = 3
Правая граница: positions[i+k] - 1 = positions[4] - 1 = 8 - 1 = 7
Подстрока [3, 7] = "A X X A B", длина = 5
Ответ: 5
Обе подстроки A B X A X и A X X A B имеют длину 5 и содержат ровно 2 буквы X.
Визуализация принципа
positions: [-1, 2, 4, 5, 8]
↑ ↑ ↑ ↑ ↑
p0 p1 p2 p3 p4
Для i=1, k=2:
p0 p1 p2 p3 p4
↓ ↓ ↓ ↓ ↓
-1 2 4 5 8
| |=========| | |
| ↑ ↑ | |
| первый X второй X |
| |
+-- можем расширить влево ---+-- можем расширить вправо --+
до p0+1 = 0 до p3-1 = 4
Код
def max_exactly_k(s, k):
# Собираем позиции X
positions = [-1] # фиктивная левая граница
for i, c in enumerate(s):
if c == 'X':
positions.append(i)
positions.append(len(s)) # фиктивная правая граница
if len(positions) - 2 < k: # меньше k букв X
return 0
max_len = 0
for i in range(1, len(positions) - k):
left = positions[i - 1] + 1 # после предыдущего X
right = positions[i + k] - 1 # до следующего X
max_len = max(max_len, right - left + 1)
return max_len
Ключевое правило Шаблона 3
┌────────────────────────────────────────────────────┐
│ positions = [-1] + [позиции X] + [len(s)] │
│ left = positions[i - 1] + 1 │
│ right = positions[i + k] - 1 │
└────────────────────────────────────────────────────┘