Alphabetic Removals
Contest: Codeforces Round 490 (Div. 3)
Difficulty rating: 1200
Tags: implementation

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:

- if there is at least one letter 'a', remove the leftmost occurrence and stop the algorithm, otherwise go to next item;
- if there is at least one letter 'b', remove the leftmost occurrence and stop the algorithm, otherwise go to next item;
- ...
- remove the leftmost occurrence of the letter 'z' and stop the algorithm.

This algorithm removes a single letter from the string. Polycarp performs this algorithm exactly $$$k$$$ times, thus removing exactly $$$k$$$ characters.

Help Polycarp find the resulting string.

Input format:
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.

The second line contains the string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters.

Output format:
Print the string that will be obtained from $$$s$$$ after Polycarp removes exactly $$$k$$$ letters using the above algorithm $$$k$$$ times.

If the resulting string is empty, print nothing. It is allowed to print nothing or an empty line (line break).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
15 3
cccaabababaccbc

Example output:
cccbbabaccbc

Example input:
15 9
cccaabababaccbc

Example output:
cccccc

Editorial:
Let the lowercase Latin letters be indexed from $$$0$$$ to $$$25$$$.
There are exists at least two different solutions:
If $$$k = n$$$ exit the program. Otherwise, count the number of occurrences of each letter $$$i$$$ from $$$0$$$ to $$$25$$$. Let it be $$$\mathit{cnt}$$$. Now, find the (alphabetically) smallest letter that will be in the resulting string. It can be done as follows: iterate over all $$$i$$$ from $$$0$$$ to $$$25$$$, and if $$$\mathit{cnt}_i \le k$$$ then subtract it from $$$k$$$, otherwise, $$$i$$$ will be the smallest letter that will be in the resulting string. But we (possibly) need to remove some number of its leftmost occurrences. It is obvious that letters smaller than $$$i$$$ will not appear in the resulting string. Also, the $$$k$$$ leftmost occurrences of letter $$$i$$$ will be removed. Now, let's iterate over all letters in string $$$s$$$ from left to right and construct the resulting string $$$\mathit{res}$$$. If the current character of $$$s$$$ (let it be $$$s_j$$$) is smaller than $$$i$$$, then do nothing. If $$$s_j$$$ is greater than $$$i$$$, then add it to $$$\mathit{res}$$$. Otherwise $$$s_j = i$$$. If $$$k > 0$$$, then decrease $$$k$$$ by one, otherwise, add $$$s_j$$$ to $$$\mathit{res}$$$. The time complexity is $$$O(n)$$$.
Another solution is the following. Let's carry the vector of pairs $$$(s_i, i)$$$ where $$$s_i$$$ is the $$$i$$$-th character of $$$s$$$ and $$$i$$$ is its position. If we sort this vector with the standard compare function, it is easy to see that the first $$$k$$$ elements of this vector will be removed from the input string. Then if we will sort the last $$$n - k$$$ elements of this vector by its positions in the input string in increasing order, we will obtain the answer. The time complexity is $$$O(n \log n)$$$.