Замена повторяющихся символов
Дана строка 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, нужно сдвинуть левую границу окна.