Subsequence Permutation (Codeforces 1552A)
Tags: Others, strings

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).

Input: 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.

Output: For each test case, output the minimum $$$k$$$ that allows you to obtain a string sorted alphabetically, through the operation described above.

Note: In the first test case, we can choose the $$$k=2$$$ characters $$$\texttt{"_ol"}$$$ and rearrange them as $$$\texttt{"_lo"}$$$ (so the resulting string is $$$\texttt{"llo"}$$$). It is not possible to sort the string choosing strictly less than $$$2$$$ characters.In the second test case, one possible way to sort $$$s$$$ is to consider the $$$k=6$$$ characters $$$\texttt{"_o__force_"}$$$ and rearrange them as $$$\texttt{"_c__efoor_"}$$$ (so the resulting string is $$$\texttt{"ccdeefoors"}$$$). One can show that it is not possible to sort the string choosing strictly less than $$$6$$$ characters.In the third test case, string $$$s$$$ is already sorted (so we can choose $$$k=0$$$ characters).In the fourth test case, we can choose all $$$k=4$$$ characters $$$\texttt{"dcba"}$$$ and reverse the whole string (so the resulting string is $$$\texttt{"abcd"}$$$).

Sample Inputs:
4
3
lol
10
codeforces
5
aaaaa
4
dcba

Sample Outputs:
2
6
0
4

Solution (Python):
qtd = int(input())
lista = list()
for i in range(0, qtd):
    tam = int(input())
    palavra = input()
    cont = 0
    s = sorted(palavra)
    for i in range(0, tam):
        if palavra[i] != s[i]:
            cont = cont + 1
    lista.append(cont)
for i in range(0, qtd):
    print(lista[i])

Solution (Python):
for i in range(int(input())):
    n = int(input())
    s = list(map(str, input()))
    h = sorted(s)
    c = 0
    for j in range(n):
        if s[j] != h[j]:
            c = c + 1
    print(c)

Solution (Python):
for s in [*open(0)][2::2]:
    s = s[:-1]
    print(sum((x != y for (x, y) in zip(s, sorted(s)))))