codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.