Skip to content

1279: 子序列排列

题目

题目描述

给定一个长度为 $n$ 的只由小写英文字母组成的字符串。

你需要选择其中的几个字符(可以不选),任意排列它们的位置,但保持其他位置的字符不动,并且只能执行这样的操作恰好一次。

例如字符串 kokodayo,可以选择五个字符 _ok_da_o,排列成 _ok_do_a,得到字符串 kokodoya

求最少选择几个字符执行上述操作之后能够使得该字符串的字典序最小。

什么是字典序? 字典序即英文单词在字典中的顺序:在英文字典中,排列单词的顺序是先按照第一个字母以升序排列(即`a、b、c、...、 z`的顺序)。如果第一个字母一样,那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长(比如,`sigh` 和 `sight`),那么把短者排在前。

输入格式

第一行一个整数 $T$ 表示数据组数。

对于每组数据,第一行一个整数 $n$ 表示字符串长度。

第二行一个长度为 $n$ 的由小写英文字母组成的字符串 $S$。

输出格式

输出最少需要选择的字符个数。

样例输入

4 3 lol 8 acmclass 5 aaaaa 4 dcba

样例输出

2 3 0 4

数据范围

$1\leq T\leq 1000, 1\leq n \leq 50$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!