Alternating String
Contest: Codeforces Round 970 (Div. 3)
Difficulty rating: 1500
Tags: brute force, data structures, dp, greedy, implementation, strings

Sakurako really loves alternating strings. She calls a string $$$s$$$ of lowercase Latin letters an alternating string if characters in the even positions are the same, if characters in the odd positions are the same, and the length of the string is even.

For example, the strings 'abab' and 'gg' are alternating, while the strings 'aba' and 'ggwp' are not.

As a good friend, you decided to gift such a string, but you couldn't find one. Luckily, you can perform two types of operations on the string:

1. Choose an index $$$i$$$ and delete the $$$i$$$-th character from the string, which will reduce the length of the string by $$$1$$$. This type of operation can be performed no more than $$$1$$$ time;
2. Choose an index $$$i$$$ and replace $$$s_i$$$ with any other letter.

Since you are in a hurry, you need to determine the minimum number of operations required to make the string an alternating one.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$)  — the number of test cases.

The first line of each test case contains a single number $$$n$$$ ($$$1 \le n\le 2\cdot 10^5$$$)  — the length of the string.

The second line of each test case contains a string $$$s$$$, consisting of lowercase Latin letters.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the minimum number of operations required to turn the string $$$s$$$ into an alternating one.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the string ababa, you can delete the first character to get baba, which is an alternating string.

For the string acdada, you can change the first two characters to get dadada, which is an alternating string.

Example input:
10
1
a
2
ca
3
aab
5
ababa
6
acdada
9
ejibmyyju
6
bbccbc
6
abacba
5
bcbca
5
dcbdb

Example output:
1
0
1
1
2
6
2
3
1
1

Editorial:
Firstly, since first operation can be used at most 1 time, we need to use it only when string has odd length.
Let's assume that the string has even length, then we can look at characters on odd and even positions independently. So, if we change all characters on even positions to the character that which is occurs the most. Same goes to the characters on the odd position.
Now, we have case where we need to delete one character. We can make prefix sum on even positions (let's call $$$pref_1[i][c]$$$ number of $$$c$$$ on such even $$$i>j$$$ and $$$s[j]=c$$$), prefix sum on odd position (let's call it $$$pref_2[i][c]$$$. Definition same as for $$$pref_1[i][c]$$$ but with odd instead of even), suffix sum on even positions (let's call it $$$suff_1[i][c]$$$ and definition same as $$$pref_1[i][c]$$$ but with $$$j>i$$$ instead of $$$i>j$$$) and suffix sum on odd positions (let's call it $$$suff_2[i][c]$$$ and definition same as $$$pref_2[i][c]$$$ but with $$$j>i$$$ instead of $$$i>j$$$). If we delete character on index $$$i$$$, our string after $$$i$$$ shift right and changes parity for all indeces bigger then $$$i$$$, so to find how many characters $$$c$$$ there are on even positions after deleting index $$$i$$$ is $$$pref_1[i][c]+suf_2[i][c]$$$. Using this, we can try to delete each character independently and solve the task as it has even length.