Largest string

4.3

3 votes
Medium, String, Hiring, Algorithms, Greedy algorithm, Ready, Approved, String Manipulation
Problem

This task is quite simple! You are given a string STR of length N where each character of string is from the set {A, B, C, D, E, F, G, H, I, J}. Now you need to delete exactly M characters from this String STR. On deleting a character from this String, STR, the neighboring characters of this just deleted character become new neighbors.

For example, Consider the String abcd. On deleting the second character of this String, the new resultant string is : acd. On deleting the first character of this resultant String, the new resultant String is : cd. The relative order of the rest of the non-deleted characters does not change due to any deletion. Each character of String STR can be deleted at most once.

Now, there can be many ways to delete M characters. After deleting any M characters from this String STR the rest of the non-deleted characters come together to from a String S. For example, given a String abcd, you need to delete any 2 characters from this String. One of the ways to do so is deleting the 1st and the 3rd characters. After doing so, the resultant String S is bd.

So, your task here is to delete any M characters from String STR, such that the resultant String S is lexicographically largest over all possible ways to delete exactly M characters.

Print this lexicographically largest String as your answer on a new line. The length of this String has to be exactly NM

Input :

The first line contains two space separated positive integers N and M.
Second line contains string STR.

Output :

Output the lexicographically largest string that can be produced from STR by deleting exactly M characters from it.

Constraint:

1MN5×105

Sample Input
4 2
BJCE
Sample Output
JE
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For the sample, all possible strings after removing exactly 2 characters are as follows -
BJ, BC, BE, JC, JE, CE
Among these largest string is JE so our answer is JE.

Contributers:
Editor Image

?