CF1552A Subsequence Permutation

给定一个长度为 $n$ 的字符串 $s$，该字符串仅由小写英文字母组成。 你需要选择一个 $k$，其中 $0 \leq k \leq n$。然后，你可以从 $s$ 中选择 $k$ 个字符，并以任意方式重新排列它们。在此过程中，其他 $n-k$ 个字符的位置保持不变。你必须恰好执行一次这样的操作。 例如，如果 $s=\texttt{"andrea"}$，你可以选择 $k=4$ 个字符 $\texttt{"a_d_ea"}$，并将它们重新排列为 $\texttt{"d_e_aa"}$，这样操作后字符串变为 $\texttt{"dneraa"}$。 请你确定最小的 $k$，使得通过上述操作后，可以将 $s$ 按字典序排序（即操作后字符串的字符按字母顺序排列）。

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。接下来有 $t$ 组测试用例。 每组测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 40$），表示字符串的长度。 第二行包含一个字符串 $s$。保证 $s$ 只包含小写英文字母。

对于每个测试用例，输出一个整数，表示使得通过上述操作后可以将字符串按字典序排序所需选择的最小 $k$。

在第一个测试用例中，我们可以选择 $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"}$）。 由 ChatGPT 4.1 翻译