codeforces-scrape

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

999C.md (1597B)


      1 Source: https://codeforces.com/problemset/problem/999/C
      2 
      3 C. Alphabetic Removals
      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 You are given a string $s$ consisting of $n$ lowercase Latin letters. Polycarp wants to remove exactly $k$ characters ($k \le n$) from the string $s$. Polycarp uses the following algorithm $k$ times:
     22 
     23 * if there is at least one letter 'a', remove the leftmost occurrence and stop the algorithm, otherwise go to next item;
     24 * if there is at least one letter 'b', remove the leftmost occurrence and stop the algorithm, otherwise go to next item;
     25 * ...
     26 * remove the leftmost occurrence of the letter 'z' and stop the algorithm.
     27 
     28 This algorithm removes a single letter from the string. Polycarp performs this algorithm exactly $k$ times, thus removing exactly $k$ characters.
     29 
     30 Help Polycarp find the resulting string.
     31 
     32 Input
     33 
     34 The first line of input contains two integers $n$ and $k$ ($1 \le k \le n \le 4 \cdot 10^5$) — the length of the string and the number of letters Polycarp will remove.
     35 
     36 The second line contains the string $s$ consisting of $n$ lowercase Latin letters.
     37 
     38 Output
     39 
     40 Print the string that will be obtained from $s$ after Polycarp removes exactly $k$ letters using the above algorithm $k$ times.
     41 
     42 If the resulting string is empty, print nothing. It is allowed to print nothing or an empty line (line break).
     43 
     44 Examples
     45 
     46 Input
     47 
     48 ```
     49 15 3  
     50 cccaabababaccbc
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 cccbbabaccbc
     57 ```
     58 
     59 Input
     60 
     61 ```
     62 15 9  
     63 cccaabababaccbc
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 cccccc
     70 ```
     71 
     72 Input
     73 
     74 ```
     75 1 1  
     76 u
     77 ```
     78 
     79 Output