1. Идея

Нужно найти самый длинный подотрезок массива, в котором не более K различных значений.

Перебирать все подотрезки нельзя: их слишком много, порядка n^2.

Здесь подходит метод двух указателей, или скользящего окна:

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

Так мы для каждого r будем знать максимально длинный допустимый отрезок, заканчивающийся в позиции r.

2. Наблюдения

Наблюдение 1

Если отрезок [l; r] содержит не более K различных значений, то любой его подотрезок тоже содержит не более K различных значений.

Это значит, что если текущее окно стало "плохим" после добавления нового элемента справа, то исправить его можно только сдвигом левой границы вправо.

Наблюдение 2

Нужно быстро понимать:

• сколько раз каждое число встречается в текущем окне;
• сколько различных чисел сейчас внутри окна.

Для этого удобно хранить словарь cnt, где cnt[x] — количество вхождений значения x в текущем окне.

Тогда:

• когда добавляем число x справа:
  • увеличиваем cnt[x],
  • если раньше было 0, то количество различных значений увеличивается на 1;
• когда убираем число y слева:
  • уменьшаем cnt[y],
  • если стало 0, то количество различных значений уменьшается на 1.

Наблюдение 3

Левая и правая границы двигаются только вправо. Значит, каждый элемент массива будет добавлен в окно не более одного раза и удалён из окна не более одного раза. Это даёт линейную сложность.

3. Алгоритм

1. Считываем n, K и массив a.
2. Создаём:
   • словарь cnt для подсчёта частот внутри окна;
   • переменную distinct — число различных значений в текущем окне;
   • указатель l = 0 — левая граница окна;
   • переменную ans = 0 — лучший ответ.
3. Перебираем правую границу r от 0 до n - 1:
   • добавляем a[r] в окно;
   • если это значение появилось впервые, увеличиваем distinct;
   • пока distinct > K, сдвигаем l вправо:
     • убираем a[l] из окна;
     • если его количество стало 0, уменьшаем distinct;
     • увеличиваем l;
   • теперь окно снова допустимо;
   • обновляем ответ длиной текущего окна: r - l + 1.
4. Выводим ans.

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

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

Что поддерживает окно

После каждой итерации по r мы поддерживаем окно [l; r], которое удовлетворяет условию:

• в нём не более K различных значений;
• l — минимально возможная левая граница для данного r, при которой условие выполнено после всех необходимых сдвигов.

Почему это так:

• когда мы добавляем a[r], число различных значений может увеличиться;
• если оно стало больше K, мы двигаем l вправо, пока снова не получим не более K различных значений;
• как только цикл while закончился, окно снова корректно.

Почему не пропускается лучший ответ

Рассмотрим любой допустимый подотрезок [L; R].

Когда алгоритм обработает позицию R как правую границу, он построит некоторое допустимое окно [l; R]. Поскольку l сдвигается только тогда, когда без этого условие нарушается, после завершения while окно [l; R] является допустимым.

Если существовал бы допустимый отрезок, заканчивающийся в R и имеющий длину больше, чем текущее окно, значит его левая граница была бы левее l. Но тогда окно с более левой границей тоже было бы допустимым, а значит l не нужно было бы сдвигать так далеко. Противоречие.

Следовательно, для каждого R алгоритм находит максимальную длину допустимого отрезка, заканчивающегося в R.

Остаётся взять максимум по всем R. Это и будет ответ на задачу.

5. Сложность

• Каждый элемент добавляется в окно один раз.
• Каждый элемент удаляется из окна не более одного раза.

Итоговая сложность:

• по времени: O(n) в среднем при использовании хеш-таблицы;
• по памяти: O(n) в худшем случае, если в окне много разных значений.

6. Код на C++17

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    int n, K;
    cin >> n >> K;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    unordered_map<long long, int> cnt;
    int distinct = 0;
    int l = 0;
    int ans = 0;

    for (int r = 0; r < n; r++) {
        cnt[a[r]]++;
        if (cnt[a[r]] == 1) {
            distinct++;
        }

        while (distinct > K) {
            cnt[a[l]]--;
            if (cnt[a[l]] == 0) {
                distinct--;
            }
            l++;
        }

        int len = r - l + 1;
        if (len > ans) {
            ans = len;
        }
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

n, K = map(int, input().split())
a = list(map(int, input().split()))

cnt = {}
distinct = 0
l = 0
ans = 0

for r in range(n):
    x = a[r]
    cnt[x] = cnt.get(x, 0) + 1
    if cnt[x] == 1:
        distinct += 1

    while distinct > K:
        y = a[l]
        cnt[y] -= 1
        if cnt[y] == 0:
            distinct -= 1
        l += 1

    length = r - l + 1
    if length > ans:
        ans = length

print(ans)