CodeForces （字符串从字母a开始删除k个字母）

You are given a string s consisting of n lowercase Latin letters. Polycarp wants to remove exactly k characters (k≤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

The first line of input contains two integers n and k (1≤k≤n≤4⋅10⁵) — 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

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

Examples

Input 1

cccaabababaccbc

Output 1

cccbbabaccbc

Input 2

cccaabababaccbc

Output 2

cccccc

Input 3

Output 3

思路：

类比桶排序，用桶来存字母的个数

代码：

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <string>

 #include <math.h>

 #include <algorithm>

 #include <vector>

 #include <stack>

 #include <queue>

 #include <set>

 #include <map>

 #include <math.h>

 const int INF=0x3f3f3f3f;

 typedef long long LL;

 const int mod=1e9+;

 const int maxn=*1e5+;

 using namespace std;

 char str[maxn];

 int cnt[];//原来字母的个数

 int num[];//处理后字母的个数 

 int main()

 {

     int n,k;

     scanf("%d %d",&n,&k);

     getchar();

     for(int i=;i<n;i++)

     {

         scanf("%c",&str[i]);

         cnt[str[i]-'a'+]++;

         num[str[i]-'a'+]++;

     }

     str[n]=;

     for(int i=;i<=;i++)//从'a'开始进行k次处理

     {

         while(num[i]&&k)

         {

             num[i]--;

             k--;

         }

     }

     for(int i=;str[i];i++)

     {

         if(cnt[str[i]-'a'+]>num[str[i]-'a'+])//说明该位置字母已删除

         {

             cnt[str[i]-'a'+]--;

             continue;

         }

         else //若该位置字母没被删，输出该字母

             printf("%c",str[i]);

     }

     return ;

 }

巴特西