Ctrl K

Наименьшая выборка с обязательной буквой

Сложная
Дана строка text, число length, буква letter и число times. Выберите из text ровно length символов, не меняя их порядок (то есть возьмите подпоследовательность), так чтобы буква letter встречалась среди них не меньше times раз. Из всех таких подпоследовательностей верните лексикографически наименьшую — ту, что раньше всех стояла бы в словаре. Гарантируется, что letter встречается в text хотя бы times раз, так что ответ всегда существует.
Пример 1
text="banana", length=3, letter="n", times=2 → 'ann'

Две буквы из трёх обязаны быть n, а третья — как можно меньше: a перед двумя n даёт ann.

Пример 2
text="zebra", length=2, letter="z", times=1 → 'za'

z стоит в самом начале, без неё нельзя, поэтому она идёт первой. Дальше берём самую маленькую букву после неё — a.

Пример 3
text="cabbac", length=4, letter="c", times=2 → 'caac'
Ограничения
  • 1 ≤ times ≤ length ≤ len(text) ≤ 5 · 10⁴
  • text состоит из строчных латинских букв
  • letter — строчная латинская буква, встречается в text не меньше times раз
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиКаждая буква по разу СредняяВычеркнуть цифры ради минимума СредняяПо бусине каждого цвета СредняяНаибольшее число из двух рядов СложнаяПартии для сортировки с повторами Сложная
загружаем Python…
Вход
text="banana", length=3, letter="n", times=2
Ожидается
'ann'

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 46 тестов на сервере, включая скрытые.