← 返回题目列表

Codeforces · 1552/A

A. 子序列排列

中文机器翻译题面 查看原题

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

您必须在 $$$0$$$ 和 $$$n$$$ 之间选择一些数字 $$$k$$$。然后,您选择 $$$s$$$ 的 $$$k$$$ 个字符并根据需要对它们进行排列。在这个过程中,其他$$$n-k$$$字符的位置保持不变。您必须执行此操作一次。

例如,如果 $$$s=\texttt{"andrea"}$$$,您可以选择 $$$k=4$$$ 字符 $$$\texttt{"a_d_ea"}$$$ 并将它们排列成 $$$\texttt{"d_e_aa"}$$$,这样操作后字符串就变成$$$\texttt{"dneraa"}$$$。

确定最小$$$k$$$,以便可以按字母顺序对$$$s$$$ 进行排序(即,在操作之后,其字符按字母顺序出现)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 40$$$) — 字符串的长度。

每个测试用例的第二行包含字符串$$$s$$$。保证 $$$s$$$ 仅包含英文字母表中的小写字母。

输出

对于每个测试用例,通过上述操作,输出允许您获得按字母顺序排序的字符串的最小$$$k$$$。

示例

输入 #1

4
3
lol
10
codeforces
5
aaaaa
4
dcba

输出 #1

2
6
0
4

注意

在第一个测试用例中,我们可以选择 $$$k=2$$$ 字符 $$$\texttt{"_ol"}$$$ 并将它们重新排列为 $$$\texttt{"_lo"}$$$ (因此生成的字符串是 $$$\texttt{"llo"}$$$)。无法严格选择少于 $$$2$$$ 字符的字符串进行排序。

在第二个测试用例中,对 $$$s$$$ 进行排序的一种可能方法是考虑 $$$k=6$$$ 字符 $$$\texttt{"_o__force_"}$$$ 并将它们重新排列为 $$$\texttt{"_c__efoor_"}$$$ (因此结果字符串是 $$$\texttt{"ccdeefoors"}$$$)。可以看出,不可能对严格选择少于 $$$6$$$ 字符的字符串进行排序。

在第三个测试用例中,字符串 $$$s$$$ 已经排序(因此我们可以选择 $$$k=0$$$ 个字符)。

在第四个测试用例中,我们可以选择所有 $$$k=4$$$ 字符 $$$\texttt{"dcba"}$$$ 并反转整个字符串(因此结果字符串是 $$$\texttt{"abcd"}$$$)。