2008E.md (2028B)
1 Source: https://codeforces.com/problemset/problem/2008/E 2 3 E. Alternating String 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 For example, the strings 'abab' and 'gg' are alternating, while the strings 'aba' and 'ggwp' are not. 24 25 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: 26 27 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; 28 2. Choose an index $i$ and replace $s_i$ with any other letter. 29 30 Since you are in a hurry, you need to determine the minimum number of operations required to make the string an alternating one. 31 32 Input 33 34 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 35 36 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. 37 38 The second line of each test case contains a string $s$, consisting of lowercase Latin letters. 39 40 It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$. 41 42 Output 43 44 For each test case, output a single integer — the minimum number of operations required to turn the string $s$ into an alternating one. 45 46 Example 47 48 Input 49 50 ``` 51 10 52 53 1 54 55 a 56 57 2 58 59 ca 60 61 3 62 63 aab 64 65 5 66 67 ababa 68 69 6 70 71 acdada 72 73 9 74 75 ejibmyyju 76 77 6 78 79 bbccbc 80 81 6 82 83 abacba 84 85 5 86 87 bcbca 88 89 5 90 91 dcbdb 92 ``` 93 94 Output 95 96 ``` 97 1 98 0 99 1 100 1 101 2 102 6 103 2 104 3 105 1 106 1 107 ``` 108 109 Note 110 111 For the string ababa, you can delete the first character to get baba, which is an alternating string. 112 113 For the string acdada, you can change the first two characters to get dadada, which is an alternating string.