А. Лучшая научная лаборатория

Условие

А. Лучшая научная лаборатория

В некотором городе несколько научных лабораторий занимаются исследованием бактериальных культур. Они изучают последовательность образцов, где каждый образец принадлежит к определённому штамму (типу бактерий). Главный биологический научно-исследовательский университет объявил конкурс: необходимо найти максимальное количество последовательных образцов, которые можно проанализировать с учётом ограничения. А именно: в любом непрерывном отрезке исследуемой последовательности должно находиться не более K различных штаммов.

Наша лаборатория стремится стать лучшей в городе. Чтобы победить в конкурсе, нам нужно найти именно такую максимальную длину отрезка, который удовлетворяет строгому условию. Мы очень надеемся на вас, ведь в случае победы лаборатория получит грант, который откроет новые горизонты для наших исследований.

Формат ввода
В первой строке заданы два числа: N — длина последовательности образцов и K — ограничение на количество различных штаммов.
На второй строке заданы N чисел — элементы последовательности.

Формат вывода
Программа должна вывести число с максимальной длиной отрезка последовательности образцов.

Пример 1
Ввод
[phone]

Вывод
3

Ответ

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

n, k = map(int, input().split())
a = list(map(int, input().split()))
counts = {}
left = best = 0
for right, value in enumerate(a):
    counts[value] = counts.get(value, 0) + 1
    while len(counts) > k:
        old = a[left]
        counts[old] -= 1
        if counts[old] == 0:
            del counts[old]
        left += 1
    best = max(best, right - left + 1)
print(best)

Каждый элемент входит в окно и выходит из него не более одного раза: ожидаемое время O(n) при хеш-таблице, память счётчиков O(min(n, K+1)). При K = 0 ответ 0. Хранить все возможные подотрезки не требуется.