Subsequence Permutation solution codeforces
A stringof length , consisting of lowercase letters of the English alphabet, is given.
You must choose some numberbetween and . Then, you select characters of and permute them however you want. In this process, the positions of the other characters remain unchanged. You have to perform this operation exactly once.
For example, if, you can choose the characters and permute them into so that after the operation the string becomes .
Determine the minimumso that it is possible to sort alphabetically (that is, after the operation its characters appear in alphabetical order).
The first line contains a single integer( ) — the number of test cases. Then test cases follow.
The first line of each test case contains one integer( ) — the length of the string.
The second line of each test case contains the string. It is guaranteed that contains only lowercase letters of the English alphabet.
For each test case, output the minimumthat allows you to obtain a string sorted alphabetically, through the operation described above.
4 3 lol 10 codeforces 5 aaaaa 4 dcba
2 6 0 4
In the first test case, we can choose the characters and rearrange them as (so the resulting string is ). It is not possible to sort the string choosing strictly less than characters.
In the second test case, one possible way to sort is to consider the characters and rearrange them as (so the resulting string is ). One can show that it is not possible to sort the string choosing strictly less than characters.
In the third test case, string is already sorted (so we can choose characters).
In the fourth test case, we can choose all characters and reverse the whole string (so the resulting string is ).