01 Идея метода
Два указателя left и right ограничивают окно — подстроку. Оба двигаются только вправо → сложность O(n).
Строка: A B X A X X A B A
↑ ↑
left right
└───────┘
окно (подстрока)
💡 Шаблон 1 — «НЕ БОЛЕЕ K раз» Найти максимальную подстроку, где символ X встречается не более K раз.
1. Двигаем right вправо, добавляя символы
2. Если условие нарушено (count > K) — двигаем left вправо
3. Окно всегда валидно → обновляем максимум
02 Пошаговый разбор
Строка ABXAXXAB, символ X, не более K=2 раз. Нажимайте «Шаг».
Интерактивный разбор · скользящее окно
Нажмите «Шаг» или «Играть»
03 Код
def max_at_most_k(s, k):
left = 0
count_x = 0
max_len = 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
max_len = max(max_len, right - left + 1)
return max_len
⚠️ Ключевое правило while count > k — сужаем ПОКА нарушено.
Обновляем max_len ПОСЛЕ while — окно уже валидно.
04 Песочница
Введите свою строку, целевой символ и K — и посмотрите работу алгоритма пошагово.
Песочница · своя задача
Нажмите «Применить», затем «Шаг»
💡 Нажмите на строку теста ниже — она подставится автоматически
05 Тесты
Попробуй · тестирование
ABXAXXAB X ≤ 2 Ответ: ?
AABXBXXBA X ≤ 1 Ответ: ?
XXXXX X ≤ 0 Ответ: ?
ABCABC X ≤ 2 Ответ: ?
XAXBXAXBXA X ≤ 3 Ответ: ?