codeforces-scrape

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

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".