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

118. Разные отрезки маршрута длины k

Сложная

Строка route — коды сортировочных центров, через которые прошли посылки Ozon за сутки, по одной букве на шаг. Дано число k ≥ 1.

Верните количество различных подстрок route длины k. Если k больше длины строки, ответ 0.

В работе: Сколько разных цепочек из `k` сортировочных центров реально встречается в логистике — столько шаблонов маршрута держать в кэше.

Пример 1

Ввод
route = "abcabca"
k = 3
Вывод
3

Окна: abc, bca, cab, abc, bca — различных три.

Пример 2

Ввод
route = "aaaa"
k = 2
Вывод
1

Все окна — «aa».

Ограничения

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

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