Код Senior Скользящее окно обновлено
Самая длинная серия после k замен
Условие
Строка из заглавных латинских букв. Можно заменить не более k символов. Длина самой длинной серии одинаковых символов, которую можно получить.
Примеры
characterReplacement("ABAB", 2) // 4
characterReplacement("AABABBA", 1) // 4
characterReplacement("A", 0) // 1
Как подойти
Условие окна: длина минус частота самого частого символа ≤ k. Тонкость, которую любят спрашивать: maxCount можно не уменьшать при сжатии - ответ от этого не испортится, потому что окно всё равно не станет длиннее уже найденного.
Подсказки: 2
- Окно допустимо, если количество символов, которые надо заменить, не больше k.
- Заменить надо все, кроме самого частого символа окна.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.
Термины по теме
Ещё по теме «Скользящее окно»
- Самая длинная серия единиц с k заменами
- Максимальная сумма окна длины k
- Максимум гласных в окне
- Кратчайший подмассив с суммой ≥ target
- Самая короткая подстрока с k различными
- Самая длинная подстрока без повторов: где начинается
- Лучшие k дней подряд по выручке
- Минимальное окно, содержащее все символы шаблона