本题要求我们从给定的字符串中删除 m 个字符,得到剩余的字符串,并且使得这个剩余字符串的字典序最小。字典序的比较就是按字符的大小顺序来比较字符串,越小的字符越靠前。
我们需要删除 m 个字符,剩下的字符形成一个新的字符串。这要求我们保持剩余字符串的字典序最小。假设我们能选择某个字符删除,它是否对最终的字典序有影响呢?答案是有的,如果当前字符的字典序比后面的字符大,删除它可能会使得后面的字符能够更早地出现在结果字符串中,从而可能使字典序变得更小。
小蓝有一串由小写字母组成的古老铭文,他希望从中删去正好 m 个字母,保持剩余字母的相对顺序不变,使得剩下的字母序列在自然比较规则下尽可能小。对于两个长度相等的字母序列,从左到右依次比较对应位置的字母。在第一个不同的位置上,字母序更靠前(即 ASCII 码更小)的序列视为更小。你的任务是求出删减后得到的最小序列。
已知铭文长度 n 满足 2≤n≤105,删除数量 m 满足 1≤m<n。测试数据组数 T 不超过 5。铭文仅由小写字母组成。
第一行包含一个整数 T,表示测试数据组数。接下来对于每组数据:第一行包含两个整数 n 和 m,分别表示序列长度和需要删除的字母个数。第二行包含一个长度为 n 的小写字母序列,字母连续给出。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.