Шаблон 4 — "РОВНО K раз", считаем КОЛИЧЕСТВО подстрок
Задача-пример
Сколько подстрок содержат букву X ровно 2 раза?
Строка: A X X A
Принцип
Количество(ровно K) = Количество(не более K) − Количество(не более K-1)
Пошаговый разбор
Сначала посчитаем подстроки с не более 2 букв X:
Строка: A X X A
0 1 2 3
Для "не более K" считаем: на каждом шаге все подстроки, заканчивающиеся в right.
right=0: окно [0,0]="A", подстроки: "A" → +1
right=1: окно [0,1]="AX", подстроки: "AX", "X" → +2
right=2: окно [0,2]="AXX", подстроки: "AXX", "XX", "X" → +3
right=3: окно [0,3]="AXXA", подстроки: "AXXA", "XXA", "XA", "A" → +4
Итого "не более 2": 1 + 2 + 3 + 4 = 10
Теперь посчитаем подстроки с не более 1 буквы X:
right=0: окно [0,0]="A" → +1
right=1: окно [0,1]="AX" → +2
right=2: count=2 > 1, сужаем до [2,2]="X" → +1
right=3: окно [2,3]="XA" → +2
Итого "не более 1": 1 + 2 + 1 + 2 = 6
Ответ
Ровно 2 = (не более 2) − (не более 1) = 10 − 6 = 4
Проверим: подстроки с ровно 2 буквами X:
- "AXX" (позиции 0-2)
- "XX" (позиции 1-2)
- "XXA" (позиции 1-3)
- "AXXA" (позиции 0-3)
Код
def count_exactly_k(s, k):
def count_at_most(k):
if k < 0:
return 0
left = 0
count_x = 0
result = 0
for right in range(len(s)):
if s[right] == 'X':
count_x += 1
while count_x > k:
if s[left] == 'X':
count_x -= 1
left += 1
result += right - left + 1 # все подстроки [left..right], [left+1..right], ...
return result
return count_at_most(k) - count_at_most(k - 1)
Ключевое правило Шаблона 4
┌──────────────────────────────────────────────────┐
│ exactly(K) = atMost(K) − atMost(K − 1) │
│ На каждом шаге: result += right − left + 1 │
└──────────────────────────────────────────────────┘
Часть 7. Сводная таблица шаблонов
| Шаблон |
Условие |
Ищем |
While |
Где обновляем |
Формула |
| 1 |
не более K |
MAX длины |
count > k |
ПОСЛЕ while |
max(len) |
| 2 |
не менее K |
MIN длины |
count >= k |
ВНУТРИ while |
min(len) |
| 3 |
ровно K |
MAX длины |
— |
через позиции |
pos[i+k] - pos[i-1] - 2 |
| 4 |
ровно K |
КОЛИЧЕСТВО |
— |
разность |
atMost(k) - atMost(k-1) |
Часть 8. Как определить шаблон по условию задачи
┌─────────────────────────────────────────────────────────────┐
│ ЧИТАЕМ УСЛОВИЕ │
├─────────────────────────────────────────────────────────────┤
│ │
│ "не более K раз" ──────────────→ ШАБЛОН 1 │
│ + максимум while count > k │
│ обновляем ПОСЛЕ │
│ │
├─────────────────────────────────────────────────────────────┤
│ │
│ "не менее K раз" ──────────────→ ШАБЛОН 2 │
│ + минимум while count >= k │
│ обновляем ВНУТРИ │
│ │
├─────────────────────────────────────────────────────────────┤
│ │
│ "ровно K раз" ──┬───────────→ ШАБЛОН 3 (если MAX) │
│ │ через позиции │
│ │ │
│ └───────────→ ШАБЛОН 4 (если СКОЛЬКО)│
│ atMost(k) - atMost(k-1)│
│ │
├─────────────────────────────────────────────────────────────┤
│ │
│ "более K раз" ══════════════ то же что "не менее K+1"│
│ │
└─────────────────────────────────────────────────────────────┘
Часть 9. Разбор реальных задач ЕГЭ
Задача 205 — Шаблон 1
Текстовый файл содержит только заглавные буквы латинского алфавита.
Определите максимальное количество идущих подряд символов,
среди которых буква A встречается не более пяти раз.
Анализ: "не более" + "максимальное" → Шаблон 1
def solve_205(filename):
with open(filename) as f:
s = f.read().strip()
left = 0
count_a = 0
max_len = 0
for right in range(len(s)):
if s[right] == 'A':
count_a += 1
while count_a > 5:
if s[left] == 'A':
count_a -= 1
left += 1
max_len = max(max_len, right - left + 1)
return max_len
Задача 284 — Шаблон 1 с несколькими счётчиками
Определите максимальное количество идущих подряд символов,
среди которых каждая из букв X, Y, Z встречается не более трёх раз.
Анализ: "каждая не более" + "максимальное" → Шаблон 1, но с проверкой всех счётчиков
def solve_284(filename):
with open(filename) as f:
s = f.read().strip()
left = 0
counts = {'X': 0, 'Y': 0, 'Z': 0}
max_len = 0
for right in range(len(s)):
if s[right] in counts:
counts[s[right]] += 1
# Сужаем пока ЛЮБОЙ счётчик > 3
while counts['X'] > 3 or counts['Y'] > 3 or counts['Z'] > 3:
if s[left] in counts:
counts[s[left]] -= 1
left += 1
max_len = max(max_len, right - left + 1)
return max_len
Задача 297 (ЕГЭ-2024) — Шаблон 2 с парами
Определите минимальное количество идущих подряд символов,
среди которых пара символов AF встречается более 200 раз.
Анализ: "более 200" = "не менее 201", "минимальное" → Шаблон 2
Особенность: считаем пары AF, а не отдельные символы!
def solve_297(filename):
with open(filename) as f:
s = f.read().strip()
left = 0
count_af = 0
min_len = float('inf')
for right in range(len(s)):
# Появилась новая пара AF?
if right > 0 and s[right-1] == 'A' and s[right] == 'F':
count_af += 1
# Условие: более 200 = не менее 201
while count_af >= 201:
min_len = min(min_len, right - left + 1) # ВНУТРИ
# Удаляем пару AF при сдвиге left?
if s[left] == 'A' and left + 1 <= right and s[left+1] == 'F':
count_af -= 1
left += 1
return min_len
Задача 280 — Шаблон 3 (два условия "ровно")
Определите максимальное количество идущих подряд символов,
среди которых буквы X и Y встречаются ровно по одному разу.
Анализ: "ровно по одному" + "максимальное" → Шаблон 3, но для двух букв
def solve_280(filename):
with open(filename) as f:
s = f.read().strip()
# Позиции X и Y с границами
pos_x = [-1] + [i for i, c in enumerate(s) if c == 'X'] + [len(s)]
pos_y = [-1] + [i for i, c in enumerate(s) if c == 'Y'] + [len(s)]
max_len = 0
# Перебираем каждую X (кроме границ)
for i in range(1, len(pos_x) - 1):
# Перебираем каждую Y (кроме границ)
for j in range(1, len(pos_y) - 1):
# Границы, где ровно 1 X и ровно 1 Y
left = max(pos_x[i-1], pos_y[j-1]) + 1
right = min(pos_x[i+1], pos_y[j+1]) - 1
# Проверяем, что обе буквы внутри [left, right]
if left <= pos_x[i] <= right and left <= pos_y[j] <= right:
max_len = max(max_len, right - left + 1)
return max_len
Задача 295 (ЕГЭ-2024) — Шаблон 1 с парами
Определите максимальное количество идущих подряд символов,
среди которых пара символов DE встречается не более 240 раз.
Анализ: "не более" + "максимальное" → Шаблон 1
def solve_295(filename):
with open(filename) as f:
s = f.read().strip()
left = 0
count_de = 0
max_len = 0
for right in range(len(s)):
if right > 0 and s[right-1] == 'D' and s[right] == 'E':
count_de += 1
while count_de > 240:
if s[left] == 'D' and left + 1 <= right and s[left+1] == 'E':
count_de -= 1
left += 1
max_len = max(max_len, right - left + 1)
return max_len
Задача 296 (ЕГЭ-2024) — Шаблон 3 с парами
Определите максимальное количество идущих подряд символов,
среди которых пара символов CD встречается ровно 160 раз.
Анализ: "ровно" + "максимальное" → Шаблон 3, но для пар
def solve_296(filename):
with open(filename) as f:
s = f.read().strip()
k = 160
# Позиции пар CD (индекс = позиция буквы C)
cd_pos = [-2] # граница (чтобы -2+2=0)
for i in range(len(s) - 1):
if s[i] == 'C' and s[i+1] == 'D':
cd_pos.append(i)
cd_pos.append(len(s)) # граница
if len(cd_pos) - 2 < k:
return 0
max_len = 0
for i in range(1, len(cd_pos) - k):
# Левая граница: после предыдущей пары (+2, т.к. пара = 2 символа)
left = cd_pos[i - 1] + 2
# Правая граница: перед следующей парой
right = cd_pos[i + k] - 1
max_len = max(max_len, right - left + 1)
return max_len
Часть 10. Домашнее задание
Уровень 1 — Шаблон 1 (базовый)
- 206 — буквы A, B, X в сумме не более 5 раз
- 207 — гласные (A,E,I,O,U,Y) в сумме не более 5 раз
- 283 — X и Y в сумме не более 5 раз
- 285 — каждая гласная не более 8 раз
Уровень 2 — Шаблон 1 с парами
- 208 — подстрока "2022" не более 4 раз
- 295 — пара DE не более 240 раз
Уровень 3 — Шаблон 2
- 297 — пара AF более 200 раз, минимум
- 367 — не менее 100000 слов, минимум
Уровень 4 — Шаблон 3
- 280 — X и Y ровно по 1 разу
- 281 — X, Y, Z ровно по 5 раз
- 296 — пара CD ровно 160 раз
Шпаргалка
┌──────────────────────────────────────────────────────────┐
│ │
│ "НЕ БОЛЕЕ K" + МАКСИМУМ → while count > k │
│ обновляем ПОСЛЕ │
│ │
│ "НЕ МЕНЕЕ K" + МИНИМУМ → while count >= k │
│ обновляем ВНУТРИ │
│ │
│ "РОВНО K" + МАКСИМУМ → через позиции │
│ left = pos[i-1] + 1 │
│ right = pos[i+k] - 1 │
│ │
│ "РОВНО K" + КОЛИЧЕСТВО → atMost(k) - atMost(k-1)│
│ │
└──────────────────────────────────────────────────────────┘