Codeforces Round 656 (Div. 3) |
---|
Finished |
You are given a string $$$s[1 \dots n]$$$ consisting of lowercase Latin letters. It is guaranteed that $$$n = 2^k$$$ for some integer $$$k \ge 0$$$.
The string $$$s[1 \dots n]$$$ is called $$$c$$$-good if at least one of the following three conditions is satisfied:
For example: "aabc" is 'a'-good, "ffgheeee" is 'e'-good.
In one move, you can choose one index $$$i$$$ from $$$1$$$ to $$$n$$$ and replace $$$s_i$$$ with any lowercase Latin letter (any character from 'a' to 'z').
Your task is to find the minimum number of moves required to obtain an 'a'-good string from $$$s$$$ (i.e. $$$c$$$-good string for $$$c=$$$ 'a'). It is guaranteed that the answer always exists.
You have to answer $$$t$$$ independent test cases.
Another example of an 'a'-good string is as follows. Consider the string $$$s = $$$"cdbbaaaa". It is an 'a'-good string, because:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.
The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 131~072$$$) — the length of $$$s$$$. It is guaranteed that $$$n = 2^k$$$ for some integer $$$k \ge 0$$$. The second line of the test case contains the string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters.
It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).
For each test case, print the answer — the minimum number of moves required to obtain an 'a'-good string from $$$s$$$ (i.e. $$$c$$$-good string with $$$c =$$$ 'a'). It is guaranteed that the answer exists.
6 8 bbdcaaaa 8 asdfghjk 8 ceaaaabb 8 bbaaddcc 1 z 2 ac
0 7 4 5 1 1
Name |
---|