9485 - 去重(remove)
时间限制 : 1 秒
内存限制 : 256 MB
给你一个字符串s,请你去除字符串中重复的字母,使得每个字母至少出现l次,至多出现r次。需保证返回结果的字典序最小,并且不能打乱字符的相对位置。如果原本字符串某种字符只出现了l^{'} (l^{'} < l )次,那么这种字符全都需要保留。
对于字典序,如果一个字符串a是字符串b的前缀串,那么a的字典序要小于b的字典序;如果不是,那么就比较他们之间第一个不同的字符的ACSII码值,值小的字典序更小。
输入
从文件remove.in中读入数据。输入的第一行为两个数字l、r。
输入的第二行为字符串s。所有字符均为小写的英文字母。
输出
输出到文件remove.out中。输出一行,为去掉部分的字符的剩余字符串。
样例
输入
1 2 bcabc
输出
abc
输入
2 3 aaabcccc
输出
aaabcc
提示
【样例1解释】
各种字符至少保留1个,至多保留2个。满足条件的剩余字符串有‘cab’、‘bcabc’、‘bcac’、‘babc’、‘cabc’、‘abc’是不同字符最多两次至少一次出现并且保证原字符顺序不变的所有可能,但是‘abc’的字典序最小。
【样例2解释】
各种字符需要保留2~3个。但是字母b只有一个,那么必须保留。‘aaabcc’、 ‘aabccc’、 ‘aaabccc’、 ‘aabccc’都满足条件,其中‘aaabcc’的字典序最小。
对于所有测试数据保证:1≤length(s)≤10^6,s_i∈[a-z],1≤ l≤r≤length(s)
来源
云南编程挑战赛