424. Longest Repeating Character Replacement

Задача

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

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

Примеры

Пример 1

Input: s = "ABAB", k = 2
Output: 4

Пояснение

Заменить две ‘A’ на ‘B’ или наоборот.

Пример 2

Input: s = "AABABBA", k = 1
Output: 4

Пояснение

Заменить ‘A’ в середине на ‘B’ → “AABBBBA”. Подстрока “BBBB” даёт 4.

Решение

Решение

/**
 * Временная сложность: O(N) — проходим по строке один раз (left и right указатели)
 * Пространственная сложность: O(26) -> O(1) — храним частоты только для английских букв
 */
var characterReplacement = function(s, k) {
    let left = 0;
    let right = 0;
    let maxFreq = 0; // Самая частая буква в текущем окне
    let result = 0;
    const freq = {}; // Таблица частот
 
    // Идем правым указателем до конца строки
    while (right < s.length) {
        const char = s[right];
 
        // 1. Добавляем букву справа в статистику
        freq[char] = (freq[char] || 0) + 1;
 
        // 2. Обновляем maxFreq (нам не нужно искать заново, просто сравниваем с новой буквой)
        maxFreq = Math.max(maxFreq, freq[char]);
 
        // 3. Текущая длина окна
        const windowLength = right - left + 1;
 
        // 4. Проверяем валидность окна
        // Если (Длина - СамаяЧастая) > k, значит нам не хватает k, чтобы заменить остальные
        if (windowLength - maxFreq > k) {
            // Окно невалидно -> сдвигаем левый край
            freq[s[left]]--; // Убираем левую букву из статистики
            left++; // Сдвигаем границу
            // Важно: maxFreq уменьшать не обязательно (хитрость алгоритма), 
            // так как результат зависит только от максимального окна, которое мы уже нашли.
        }
 
        // 5. Обновляем результат (длина окна)
        result = Math.max(result, right - left + 1);
 
        right++;
    }
 
    return result;
};