940C.md (1974B)
1 Source: https://codeforces.com/problemset/problem/940/C 2 3 C. Phone Numbers 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 And where the are the phone numbers? 22 23 You are given a string *s* consisting of lowercase English letters and an integer *k*. Find the lexicographically smallest string *t* of length *k*, such that its set of letters is a subset of the set of letters of *s* and *s* is lexicographically smaller than *t*. 24 25 It's guaranteed that the answer exists. 26 27 Note that the set of letters is a set, not a multiset. For example, the set of letters of abadaba is {*a*, *b*, *d*}. 28 29 String *p* is lexicographically smaller than string *q*, if *p* is a prefix of *q*, is not equal to *q* or there exists *i*, such that *p**i* < *q**i* and for all *j* < *i* it is satisfied that *p**j* = *q**j*. For example, abc is lexicographically smaller than abcd , abd is lexicographically smaller than abec, afa is not lexicographically smaller than ab and a is not lexicographically smaller than a. 30 31 Input 32 33 The first line of input contains two space separated integers *n* and *k* (1 ≤ *n*, *k* ≤ 100 000) — the length of *s* and the required length of *t*. 34 35 The second line of input contains the string *s* consisting of *n* lowercase English letters. 36 37 Output 38 39 Output the string *t* conforming to the requirements above. 40 41 It's guaranteed that the answer exists. 42 43 Examples 44 45 Input 46 47 ``` 48 3 3 49 abc 50 ``` 51 52 Output 53 54 ``` 55 aca 56 ``` 57 58 Input 59 60 ``` 61 3 2 62 abc 63 ``` 64 65 Output 66 67 ``` 68 ac 69 ``` 70 71 Input 72 73 ``` 74 3 3 75 ayy 76 ``` 77 78 Output 79 80 ``` 81 yaa 82 ``` 83 84 Input 85 86 ``` 87 2 3 88 ba 89 ``` 90 91 Output 92 93 ``` 94 baa 95 ``` 96 97 Note 98 99 In the first example the list of strings *t* of length 3, such that the set of letters of *t* is a subset of letters of *s* is as follows: aaa, aab, aac, aba, abb, abc, aca, acb, .... Among them, those are lexicographically greater than abc: aca, acb, .... Out of those the lexicographically smallest is aca.