Longest Repeating Character Replacement

Средняя№424переменный размер

Дана строка из заглавных букв и число k. Можно заменить не больше k букв на любые другие. Найди длину самого длинного куска из одной повторяющейся буквы, который так можно получить. Наш пример: «ABABBCB» и k = 1 — ответ 4: замени «A» в «BABB» и получишь «BBBB».

424 Longest Repeating Character ReplacementРазбор · 1×

Пример: s = «ABABBCB», k = 1. В окне отмечены буквы на замену; под строкой — счётчики, наибольший отмечен как оставленный.

0A1B2A3B4B5C6Bcount—
ещё не дошлиокновходящая буквана замену или уходитвышло из окнаоставленная буква, лучшее окно

Начинаем с пустого словаря: у каждой буквы счётчик 0

01/41
сначала · назад · пуск · шаг
Скорость
1function characterReplacement(s, k):
2 count = empty map // missing keys: 0
3 left = 0
4 best = 0
5 for right from 0 to len(s) - 1:
6 count[s[right]] = count[s[right]] + 1
7 while (right - left + 1) - largest(count) > k:
8 count[s[left]] = count[s[left]] - 1
9 left = left + 1
10 best = max(best, right - left + 1)
11 return best
состояние
count
{}
left
–
right
–
best
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. В окне выгоднее всего оставить самую частую букву и заменить остальные: замен нужно столько, сколько длина минус наибольший счётчик. Окно хорошее, если замен не больше k.
  2. Хорошее окно остаётся хорошим, если убрать букву слева, поэтому для каждого right достаточно сужать, пока окно снова не станет хорошим: что осталось — самое длинное хорошее окно, которое кончается на right.
  3. Сужение может занять не один шаг: убранная буква может уменьшить наибольший счётчик, и тогда замен нужно столько же, сколько было.

Сложность

Время O(26 · n): каждая буква один раз входит и один раз выходит, а наибольший счётчик ищется среди не больше чем 26. Память O(1): не больше 26 счётчиков.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.