Войти Регистрация
Алгоритмы

210. Самый длинный период одного тарифа после k правок

Средняя

history[i] — буква тарифа абонента МТС в i-й месяц, например "A" — один тариф, "B" — другой. Часть записей — ошибки биллинга.

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

В работе: Программа лояльности считает стаж на тарифе: у абонента 120 месяцев истории и 2–3 записи с ошибкой миграции, и без исправлений стаж обнуляется посреди периода.

Пример 1

Ввод
history = "AABABBA"
k = 1
Вывод
4

Исправить B в «AABA» — 4 месяца тарифа A.

Пример 2

Ввод
history = "ABCD"
k = 0
Вывод
1

Без правок — по месяцу.

Ограничения

  • 1 ≤ n ≤ 10⁵
  • буквы A–Z
  • 0 ≤ k ≤ n
  • Лимит — 2 с на тест (1500 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def longest_one_tariff(history, k):
Скользящее окноПодсчётСтрокицельO(n)

Источник: наша задача на данных МТС. Условие пересказано своими словами.