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

You are given a string $s$

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$

Help Polycarp find the resulting string.

Input

The first line of input contains two integers $n$

The second line contains the string $s$

Output

Print the string that will be obtained from $s$

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

Examples

Input 1

15 3
cccaabababaccbc

Output 1

cccbbabaccbc

Input 2

15 9
cccaabababaccbc

Output 2

cccccc

Input 3

1 1
u

Output 3

思路：

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

代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <math.h>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 const int maxn=4*1e5+10;
17 using namespace std;
18 
19 char str[maxn];
20 int cnt[27];//原来字母的个数 
21 int num[27];//处理后字母的个数 
22 
23 int main()
24 {
25     int n,k;
26     scanf("%d %d",&n,&k);
27     getchar();
28     for(int i=0;i<n;i++)
29     {
30         scanf("%c",&str[i]);
31         cnt[str[i]-'a'+1]++;
32         num[str[i]-'a'+1]++;
33     }
34     str[n]=0;
35     for(int i=1;i<=26;i++)//从'a'开始进行k次处理 
36     {
37         while(num[i]&&k)
38         {
39             num[i]--;
40             k--;
41         }
42     }
43     for(int i=0;str[i];i++)
44     {
45         if(cnt[str[i]-'a'+1]>num[str[i]-'a'+1])//说明该位置字母已删除 
46         {
47             cnt[str[i]-'a'+1]--;
48             continue;
49         }
50         else //若该位置字母没被删，输出该字母 
51             printf("%c",str[i]);
52     }
53     return 0;
54 }