1076A.md (1495B)
1 Source: https://codeforces.com/problemset/problem/1076/A 2 3 A. Minimizing the String 4 5 time limit per test 6 7 1 second 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 You are given a string $s$ consisting of $n$ lowercase Latin letters. 22 23 You have to remove at most one (i.e. zero or one) character of this string in such a way that the string you obtain will be lexicographically smallest among all strings that can be obtained using this operation. 24 25 String $s = s_1 s_2 \dots s_n$ is lexicographically smaller than string $t = t_1 t_2 \dots t_m$ if $n \lt m$ and $s_1 = t_1, s_2 = t_2, \dots, s_n = t_n$ or there exists a number $p$ such that $p \le min(n, m)$ and $s_1 = t_1, s_2 = t_2, \dots, s_{p-1} = t_{p-1}$ and $s_p \lt t_p$. 26 27 For example, "aaa" is smaller than "aaaa", "abb" is smaller than "abc", "pqr" is smaller than "z". 28 29 Input 30 31 The first line of the input contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of $s$. 32 33 The second line of the input contains exactly $n$ lowercase Latin letters — the string $s$. 34 35 Output 36 37 Print one string — the smallest possible lexicographically string that can be obtained by removing at most one character from the string $s$. 38 39 Examples 40 41 Input 42 43 ``` 44 3 45 aaa 46 ``` 47 48 Output 49 50 ``` 51 aa 52 ``` 53 54 Input 55 56 ``` 57 5 58 abcda 59 ``` 60 61 Output 62 63 ``` 64 abca 65 ``` 66 67 Note 68 69 In the first example you can remove any character of $s$ to obtain the string "aa". 70 71 In the second example "abca" < "abcd" < "abcda" < "abda" < "acda" < "bcda".