Задача ШАДа
Дается строка s и число k. Найти длину максимального подотрезка на котором не более k различных букв.

Решение
Задача решается за O(n) с помощью двух указателей.
Давайте будем перебирать правый край отрезка, а левый будет сдвигаться до тех пор пока в подотрезке больше k различных символов. Чтобы хранить количество различных символов используем словарь. Ключем в словаре будет буква, а значение то сколько раз встречалась буква на этом подотрезки.
Таким образом получим, второй указатель двигается слева направо, а первый его догоняет. Таким образом мы рассмотрели каждую позицию не более 2 раз, соответственно асимптотика O(n)

Псевдокод в комментариях: