Замена повторяющихся символов: разбор задачи

Почему эта задача важна?

Задача "Замена повторяющихся символов" позволяет оценить:

• 🧠 Глубокое понимание техники скользящего окна
• ⚡ Навыки оптимизации решения для работы с ограничениями
• 🎯 Умение обрабатывать строки и подсчитывать частоту символов
• 🔍 Способность находить паттерны для максимизации результата

Постановка задачи

Формулировка:

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

Примеры:

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

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

// Третий пример ✅
Input: s = "ABCDE", k = 1
Output: 2
Объяснение: Можно заменить любую букву на другую, получив подстроку длиной 2.

Ограничения:

• 1 <= s.length <= 10^5
• s состоит только из заглавных английских букв
• 0 <= k <= s.length

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Подходы к решению

Решение 1: Наивный подход (перебор всех подстрок) 🔍

function characterReplacement(s, k) {
  let maxLength = 0;
  
  // Перебираем все возможные начальные позиции подстроки
  for (let i = 0; i < s.length; i++) {
    // Перебираем все возможные символы для замены
    for (const targetChar of "ABCDEFGHIJKLMNOPQRSTUVWXYZ") {
      let replacements = 0;
      let j = i;
      
      // Расширяем подстроку вправо, пока не превысим лимит замен
      while (j < s.length && (s[j] === targetChar || replacements < k)) {
        if (s[j] !== targetChar) {
          replacements++;
        }
        j++;
      }
      
      // Обновляем максимальную длину
      maxLength = Math.max(maxLength, j - i);
    }
  }
  
  return maxLength;
}

Анализ решения:

✅ Понятная логика и простая реализация

❌ Временная сложность O(n * 26 * n) = O(n²), где n - длина строки

❌ Неэффективен для длинных строк

❌ Избыточный перебор всех возможных символов

Решение 2: Скользящее окно с подсчетом частоты символов (оптимальное решение) 🚀

function characterReplacement(s, k) {
  // Массив для подсчета частоты символов в текущем окне
  const charCount = new Array(26).fill(0);
  
  let maxLength = 0;
  let left = 0;
  let maxFrequency = 0;
  
  for (let right = 0; right < s.length; right++) {
    // Увеличиваем счетчик для текущего символа
    const charIndex = s.charCodeAt(right) - 65; // 'A' имеет код 65
    charCount[charIndex]++;
    
    // Обновляем максимальную частоту символа в текущем окне
    maxFrequency = Math.max(maxFrequency, charCount[charIndex]);
    
    // Если количество замен превышает k, сдвигаем левую границу
    if (right - left + 1 - maxFrequency > k) {
      charCount[s.charCodeAt(left) - 65]--;
      left++;
    }
    
    // Обновляем максимальную длину подстроки
    maxLength = Math.max(maxLength, right - left + 1);
  }
  
  return maxLength;
}

Характеристики:

✅ Оптимальная временная сложность O(n)

✅ Пространственная сложность O(1) из-за фиксированного размера алфавита

✅ Эффективное использование техники скользящего окна

✅ Отсутствие необходимости перебирать все символы алфавита

Решение 3: Оптимизированное скользящее окно с ранним выходом 🔧

function characterReplacement(s, k) {
  const charCount = new Array(26).fill(0);
  let maxLength = 0;
  let left = 0;
  let maxFrequency = 0;
  
  for (let right = 0; right < s.length; right++) {
    const charIndex = s.charCodeAt(right) - 65;
    charCount[charIndex]++;
    
    // Обновляем максимальную частоту
    maxFrequency = Math.max(maxFrequency, charCount[charIndex]);
    
    // Ключевая оптимизация: обратите внимание, что мы не уменьшаем maxFrequency
    // при сдвиге левой границы. Это допустимо, так как нас интересует только
    // максимальная длина подстроки.
    if (right - left + 1 - maxFrequency > k) {
      charCount[s.charCodeAt(left) - 65]--;
      left++;
    }
    
    maxLength = Math.max(maxLength, right - left + 1);
    
    // Ранний выход: если осталось недостаточно символов для улучшения результата
    if (maxLength >= s.length - left) {
      break;
    }
  }
  
  return maxLength;
}

Преимущества и недостатки:

✅ Временная сложность O(n)

✅ Оптимизация с ранним выходом для длинных строк

✅ Не требует пересчета максимальной частоты при каждом сдвиге окна

❌ Немного сложнее для понимания, особенно оптимизация с maxFrequency

Решение 4: Бинарный поиск с проверкой возможности подстроки 📊

function characterReplacement(s, k) {
  // Функция для проверки, возможна ли подстрока длиной length
  function isPossible(length) {
    const charCount = new Array(26).fill(0);
    
    for (let i = 0; i < s.length; i++) {
      // Добавляем символ в окно
      charCount[s.charCodeAt(i) - 65]++;
      
      // Если окно достигло нужной длины, удаляем символ с левого края
      if (i >= length) {
        charCount[s.charCodeAt(i - length) - 65]--;
      }
      
      // Проверяем, достаточно ли у нас замен для текущего окна
      if (i >= length - 1) {
        const maxFreq = Math.max(...charCount);
        if (length - maxFreq <= k) {
          return true;
        }
      }
    }
    
    return false;
  }
  
  // Бинарный поиск для нахождения максимальной длины
  let left = 1;
  let right = s.length;
  let result = 0;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (isPossible(mid)) {
      result = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return result;
}

Особенности:

✅ Альтернативный подход к задаче

✅ Логарифмический поиск по пространству ответов

❌ Более сложная реализация

❌ Временная сложность O(n log n) из-за бинарного поиска и проверки

Интуиция за алгоритмом скользящего окна

Ключевая идея решения с скользящим окном заключается в следующем:

1. Мы поддерживаем окно символов [left, right] и подсчитываем частоту каждого символа в этом окне.
2. Для валидного окна должно выполняться условие: (длина окна) - (частота самого частого символа) ≤ k. Это означает, что нам нужно заменить не более k символов, чтобы сделать все символы в окне одинаковыми.
3. Когда окно становится невалидным, мы сдвигаем левую границу вправо.
4. Максимальная длина валидного окна и будет нашим ответом.

Интересная оптимизация: мы не обязаны уменьшать значение maxFrequency при сдвиге левой границы, поскольку нас интересует только максимальная длина окна. Если окно с большей частотой было найдено ранее, мы уже учли его в maxLength.

Рекомендации по решению 💡

1. Выбор метода решения:

   • 🚀 Скользящее окно с подсчетом частоты - оптимальный подход
   • 📝 Важно правильно определить условие валидности окна
   • 🧮 Подсчет частоты символов лучше делать через массив для быстрого доступа

2. Важные моменты:

   • 📝 Правильное обновление максимальной частоты символа
   • 🔄 Корректное условие для сдвига левой границы окна
   • 📊 Понимание, что мы ищем подстроку с одним символом после замен

Распространённые ошибки

1. 🤦‍♂️ Неправильное вычисление количества необходимых замен
2. 😅 Попытка явно находить символ для замены, вместо подсчета частот
3. 🐛 Ошибки при работе с границами окна и индексами массива

Визуализация алгоритма скользящего окна

Рассмотрим пример строки "AABABBA" с k = 1:

Начальное состояние:
s = "AABABBA", k = 1, left = 0, right = 0, maxFrequency = 0, charCount = [0,0,...,0]

Шаг 1: right = 0, символ 'A'
charCount['A'] = 1, maxFrequency = 1
Окно: "A", длина = 1, необходимо замен: 0, валидно
maxLength = 1

Шаг 2: right = 1, символ 'A'
charCount['A'] = 2, maxFrequency = 2
Окно: "AA", длина = 2, необходимо замен: 0, валидно
maxLength = 2

Шаг 3: right = 2, символ 'B'
charCount['B'] = 1, maxFrequency = 2
Окно: "AAB", длина = 3, необходимо замен: 1, валидно
maxLength = 3

Шаг 4: right = 3, символ 'A'
charCount['A'] = 3, maxFrequency = 3
Окно: "AABA", длина = 4, необходимо замен: 1, валидно
maxLength = 4

Шаг 5: right = 4, символ 'B'
charCount['B'] = 2, maxFrequency = 3
Окно: "AABAB", длина = 5, необходимо замен: 2, невалидно
Сдвигаем left: charCount['A']--
left = 1, окно: "ABAB", длина = 4, необходимо замен: 2, невалидно
Сдвигаем left: charCount['A']--
left = 2, окно: "BAB", длина = 3, необходимо замен: 1, валидно
maxLength = 4 (не изменяется)

Шаг 6: right = 5, символ 'B'
charCount['B'] = 3, maxFrequency = 3
Окно: "BABB", длина = 4, необходимо замен: 1, валидно
maxLength = 4

Шаг 7: right = 6, символ 'A'
charCount['A'] = 2, maxFrequency = 3
Окно: "BABBA", длина = 5, необходимо замен: 2, невалидно
Сдвигаем left: charCount['B']--
left = 3, окно: "BBA", длина = 4, необходимо замен: 1, валидно
maxLength = 4

Итоговый результат: maxLength = 4

Оптимизации

Использование переменной для отслеживания текущей длины окна

function characterReplacement(s, k) {
  const charCount = new Array(26).fill(0);
  let maxLength = 0;
  let left = 0;
  let maxFrequency = 0;
  let windowLength = 0;
  
  for (let right = 0; right < s.length; right++) {
    const charIndex = s.charCodeAt(right) - 65;
    charCount[charIndex]++;
    
    maxFrequency = Math.max(maxFrequency, charCount[charIndex]);
    windowLength = right - left + 1;
    
    // Если количество замен превышает k
    if (windowLength - maxFrequency > k) {
      charCount[s.charCodeAt(left) - 65]--;
      left++;
      windowLength--;
    }
    
    maxLength = Math.max(maxLength, windowLength);
  }
  
  return maxLength;
}

Оптимизация для поиска максимальной частоты

function characterReplacement(s, k) {
  const charCount = new Array(26).fill(0);
  let maxLength = 0;
  let left = 0;
  let maxFrequency = 0;
  
  for (let right = 0; right < s.length; right++) {
    const charIndex = s.charCodeAt(right) - 65;
    charCount[charIndex]++;
    
    // Оптимизированный способ обновления maxFrequency без поиска максимума во всем массиве
    if (charCount[charIndex] > maxFrequency) {
      maxFrequency = charCount[charIndex];
    }
    
    const windowLength = right - left + 1;
    
    // Если количество замен превышает k
    if (windowLength - maxFrequency > k) {
      charCount[s.charCodeAt(left) - 65]--;
      left++;
    } else {
      maxLength = Math.max(maxLength, windowLength);
    }
    
    // Ранний выход
    if (maxLength >= s.length - left) {
      break;
    }
  }
  
  return maxLength;
}

Ключевое наблюдение

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

1. Если новый символ имеет большую частоту, то maxFrequency будет корректно обновлена.
2. Если maxFrequency становится недостижимой из-за сдвига левой границы, это не влияет на результат, поскольку новое окно все равно будет либо меньше, либо равно предыдущему максимальному окну.

Эта оптимизация позволяет избежать поиска максимума в массиве частот на каждой итерации.

Заключение

При решении задачи "Замена повторяющихся символов" важно помнить:

• 🤹‍♂️ Техника скользящего окна идеально подходит для поиска подстрок с ограничениями
• 📊 Ключевое условие: (длина окна) - (максимальная частота) ≤ k
• 🧠 Не нужно явно выполнять замены, достаточно отслеживать, сколько замен потребуется

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