Codeforces Round 466 (Div. 2) |
---|
Закончено |
И где здесь телефонные номера?
Дана строка s из строчных букв английского алфавита и число k. Найдите лексикографически минимальную строку t, имеющую длину k, множество букв которой является подмножеством множества букв s и s лексикографически меньше t.
Гарантируется, что ответ существует.
Обратите внимание, что под множеством букв строки подразумевается множество, а не мультимножество. В частности, множество букв строки abadaba это {a, b, d}.
Строка p считается лексикографически меньше строки q, если p — префикс q, не равный q или существует i такое, что pi < qi и для всех j < i выполнено pj = qj. Например, abc лексикографически меньше abcd , abd лексикографически меньше abec, afa лексикографически не меньше ab и a лексикографически не меньше a.
В первой строке через пробел заданы два целых числа n и k (1 ≤ n, k ≤ 100 000) — длина строки s и необходимая длина строки t.
Во второй строке задана строка s, состоящая из n строчных букв английского алфавита.
Выведите строку t, удовлетворяющую условиям, описанным выше.
Гарантируется, что ответ существует.
3 3
abc
aca
3 2
abc
ac
3 3
ayy
yaa
2 3
ba
baa
В первом примере список строк t длины 3, подходящих под условие, что множество букв t — подмножество множества букв s, таков: aaa, aab, aac, aba, abb, abc, aca, acb, .... Из них лексикографически больше abc: aca, acb, .... Лексикографически минимальная из них — aca.
Название |
---|