Замена повторяющихся символов

Дана строка s, состоящая только из заглавных английских букв, и целое число k. Вы можете выбрать до k символов строки и заменить их любыми другими заглавными английскими буквами.

После выполнения не более k замен верните длину самой длинной подстроки, которая содержит только один уникальный символ.

Пример 1:

Input: s = "ABAB", k = 2
Output: 4
Объяснение: Можно заменить 2 'B' на 'A', получив строку "AAAA".

Пример 2:

Input: s = "AABABBA", k = 1
Output: 4
Объяснение: Можно заменить 1 'B' на 'A', получив подстроку "AAAA".
Рекомендуемая временная и пространственная сложность

Стремитесь к решению с временной сложностью O(n) и пространственной сложностью O(1), где n — длина входной строки.

Подсказка 1

Попробуйте использовать технику скользящего окна. Поддерживайте окно, в котором после k замен все символы одинаковые.

Подсказка 2

В каждом окне важно знать, сколько раз встречается самый частый символ. Разница между размером окна и частотой самого частого символа - это минимальное количество замен, необходимое для получения строки из одинаковых символов.

Подсказка 3

Используйте хеш-таблицу для подсчета частоты символов в текущем окне. Когда (размер_окна - максимальная_частота) > k, нужно сдвинуть левую границу окна.

Эта задача проверяет навыки работы со строками и оптимизации с использованием техники скользящего окна. Она помогает развить понимание алгоритмической сложности и работы с подстроками. Решение требует эффективного подхода к подсчету частоты символов и управлению размером окна.

Входные параметры :

"ABAB", 2

Ожидаемый результат

4