Самая короткая подстрока с k различными: задача по Алгоритмы

Условие

Длина самой короткой подстроки, содержащей ровно k различных символов. Нет такой - 0.

Примеры

shortestWithK("abcba", 2) // 2
shortestWithK("aaaa", 1) // 1
shortestWithK("abc", 5) // 0

Как подойти

Окно переменной длины: расширяем right, чиним left в while, фиксируем ответ. Счётчик, дошедший до нуля, обязательно удалять из Map, иначе size перестанет отражать число различных символов.

Подсказки: 2

Сжимай окно, пока различных больше k.
Удаляй ключ из Map, когда его счётчик обнулился - иначе size врёт.

Решите в тренажёре

Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.

Решить в тренажёре

Предыдущий вопрос

Кратчайший подмассив с суммой ≥ target

Следующий вопрос

Самая длинная подстрока без повторов: где начинается

Урок по теме

Паттерн: Скользящее окно

Термины по теме

Скользящее окно

Ещё по теме «Скользящее окно»

Все вопросы модуля