01 Идея шаблона
Найти максимальную подстроку, где символ X встречается ровно K раз.
💡 Принцип — через позиции 1. Собираем все позиции символа X
2. Добавляем фиктивные границы: -1 слева и len(s) справа
3. Для каждой группы из K подряд идущих X — расширяем влево и вправо до соседних X
4. Между positions[i-1] и positions[i+k] находятся ровно K символов X
⚠️ Почему не простое скользящее окно? Шаблон 1 ищет «не более K» (max), Шаблон 2 — «не менее K» (min). Для «ровно K» нужен другой подход: фиксируем K целевых символов и расширяем окно до ближайших соседей.
02 Пошаговый разбор
Строка ABXAXXAB, символ X, ровно K=2.
Интерактивный разбор · шаблон 3
Массив positions
Нажмите «Шаг» или «Авто»
03 Код
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
✅ Ключевая формула left = positions[i-1] + 1 — после предыдущего X (не включая его)
right = positions[i+k] - 1 — до следующего X (не включая его)
Между left и right ровно K символов X.
04 Песочница
Песочница · своя задача
Массив positions
Нажмите «Применить», затем «Шаг»
💡 Нажмите на строку теста ниже — она подставится автоматически
05 Тесты
Попробуй · тестирование
ABXAXXAB X = 2 Ответ: ?
XAXBXAXBXA X = 3 Ответ: ?
AAXBBXCCX X = 1 Ответ: ?
XXXXX X = 3 Ответ: ?
ABCABC X = 1 Ответ: ?
06 Сравнение всех шаблонов
| |
Шаблон 1 |
Шаблон 2 |
Шаблон 3 |
| Условие |
≤ K |
≥ K |
= K |
| Ищем |
Максимум |
Минимум |
Максимум |
| Метод |
while > k |
while ≥ k |
positions |
| Обновление |
ПОСЛЕ while |
ВНУТРИ while |
В цикле по i |