308646: CF1552A. Subsequence Permutation
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Subsequence Permutation
题意翻译
### 题目大意: 有 t 组数据,每组数据会给你一个长度为 n 的字符串 s 。 你可以选择 k 个数,并把这 k 个数排序。使字符串 s 最后按照字典序排序。输出 k 的最小值。题目描述
A string $ s $ of length $ n $ , consisting of lowercase letters of the English alphabet, is given. You must choose some number $ k $ between $ 0 $ and $ n $ . Then, you select $ k $ characters of $ s $ and permute them however you want. In this process, the positions of the other $ n-k $ characters remain unchanged. You have to perform this operation exactly once. For example, if $ s=\texttt{"andrea"} $ , you can choose the $ k=4 $ characters $ \texttt{"a_d_ea"} $ and permute them into $ \texttt{"d_e_aa"} $ so that after the operation the string becomes $ \texttt{"dneraa"} $ . Determine the minimum $ k $ so that it is possible to sort $ s $ alphabetically (that is, after the operation its characters appear in alphabetical order).输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. Then $ t $ test cases follow. The first line of each test case contains one integer $ n $ ( $ 1 \le n \le 40 $ ) — the length of the string. The second line of each test case contains the string $ s $ . It is guaranteed that $ s $ contains only lowercase letters of the English alphabet.
输出格式
For each test case, output the minimum $ k $ that allows you to obtain a string sorted alphabetically, through the operation described above.
输入输出样例
输入样例 #1
4
3
lol
10
codeforces
5
aaaaa
4
dcba
输出样例 #1
2
6
0
4