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

13. Подстрока, где не больше k разных символов

Средняя

Даны строка s и число k. Верните длину самой длинной подстроки, в которой не больше k различных символов.

При k = 0 подходит только пустая подстрока — ответ 0.

В работе: Самый длинный отрезок журнала, где задействовано не больше k разных серверов.

Пример 1

Ввод
s = "abbcab"
k = 2
Вывод
3

«abb» или «bbc».

Пример 2

Ввод
s = "zzzx"
k = 1
Вывод
3

Ограничения

  • 0 ≤ длина s ≤ 10⁶
  • 0 ≤ k ≤ 10⁵
  • Лимит — 1 с на тест.
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def longest_k_distinct(s, k):
Скользящее окноСтрокицельO(n)

Источник: отчёт о Яндексе, 2023. Условие пересказано своими словами.

Давали на собеседовании? Ответов пока мало — ваш поможет.