Задача . C. Телефонные номера

И где здесь телефонные номера?

Дана строка s из строчных букв английского алфавита и число k. Найдите лексикографически минимальную строку t, имеющую длину k, множество букв которой является подмножеством множества букв s и s лексикографически меньше t.

Гарантируется, что ответ существует.

Обратите внимание, что под множеством букв строки подразумевается множество, а не мультимножество. В частности, множество букв строки abadaba это {a, b, d}.

Строка p считается лексикографически меньше строки q, если p — префикс q, не равный q или существует i такое, что p_i < q_i и для всех j < i выполнено p_j = q_j. Например, abc лексикографически меньше abcd , abd лексикографически меньше abec, afa лексикографически не меньше ab и a лексикографически не меньше a.