01 Идея шаблона
Сколько подстрок содержат символ X ровно K раз?
💡 Трюк с вычитанием exactly(K) = atMost(K) − atMost(K−1)
Считаем «не более K» (Шаблон 1), вычитаем «не более K−1» — остаются только подстроки с ровно K.
⚠️ Подсчёт подстрок в atMost На каждом шаге прибавляем right − left + 1 — это количество подстрок, оканчивающихся в right.
02 Пошаговый разбор
Строка AXXA, символ X, ровно K=2. Два прогона синхронно.
Интерактивный разбор · два прогона
atMost(2) = ? − atMost(1) = ? = ?
03 Код
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
return result
return count_at_most(k) - count_at_most(k - 1)
04 Песочница
Песочница · своя задача
?
💡 Нажмите на строку теста — она подставится автоматически
05 Тесты
Попробуй · тестирование
AXXAX = 2Ответ:?
ABXAXXABX = 2Ответ:?
XAXBXAX = 1Ответ:?
XXXXXX = 3Ответ:?
ABCX = 1Ответ:?
06 Все 4 шаблона
| |
Ш1 |
Ш2 |
Ш3 |
Ш4 |
| Условие |
≤ K |
≥ K |
= K |
= K |
| Ищем |
max длина |
min длина |
max длина |
кол-во |
| Метод |
while |
while |
positions |
atMost−atMost |
ПримечаниеШаблон 4 — скорее олимпиадная техника. На ЕГЭ пока не встречалась, но полезна для понимания связи между «не более K» и «ровно K».