Почему это работает
- В окне выгоднее всего оставить самую частую букву и заменить остальные: замен нужно столько, сколько длина минус наибольший счётчик. Окно хорошее, если замен не больше k.
- Хорошее окно остаётся хорошим, если убрать букву слева, поэтому для каждого right достаточно сужать, пока окно снова не станет хорошим: что осталось — самое длинное хорошее окно, которое кончается на right.
- Сужение может занять не один шаг: убранная буква может уменьшить наибольший счётчик, и тогда замен нужно столько же, сколько было.
Сложность
Время O(26 · n): каждая буква один раз входит и один раз выходит, а наибольший счётчик ищется среди не больше чем 26. Память O(1): не больше 26 счётчиков.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗