1822E.md (2041B)
1 Source: https://codeforces.com/problemset/problem/1822/E 2 3 E. Making Anti-Palindromes 4 5 time limit per test 6 7 1 second 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 You are given a string $s$, consisting of lowercase English letters. In one operation, you are allowed to swap any two characters of the string $s$. 22 23 A string $s$ of length $n$ is called an anti-palindrome, if $s[i] \ne s[n - i + 1]$ for every $i$ ($1 \le i \le n$). For example, the strings "codeforces", "string" are anti-palindromes, but the strings "abacaba", "abc", "test" are not. 24 25 Determine the minimum number of operations required to make the string $s$ an anti-palindrome, or output $-1$, if this is not possible. 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows. 30 31 Each test case consists of two lines. The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the string $s$. 32 33 The second line contains the string $s$, consisting of $n$ lowercase English letters. 34 35 The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 36 37 Output 38 39 For each test case, output a single integer — the minimum number of operations required to make the string $s$ an anti-palindrome, or $-1$ if this is not possible. 40 41 Example 42 43 Input 44 45 ``` 46 10 47 48 10 49 50 codeforces 51 52 3 53 54 abc 55 56 10 57 58 taarrrataa 59 60 10 61 62 dcbdbdcccc 63 64 4 65 66 wwww 67 68 12 69 70 cabbaccabaac 71 72 10 73 74 aadaaaaddc 75 76 14 77 78 aacdaaaacadcdc 79 80 6 81 82 abccba 83 84 12 85 86 dcbcaebacccd 87 ``` 88 89 Output 90 91 ``` 92 0 93 -1 94 1 95 1 96 -1 97 3 98 -1 99 2 100 2 101 2 102 ``` 103 104 Note 105 106 In the first test case, the string "codeforces" is already an anti-palindrome, so the answer is $0$. 107 108 In the second test case, it can be shown that the string "abc" cannot be transformed into an anti-palindrome by performing the allowed operations, so the answer is $-1$. 109 110 In the third test case, it is enough to swap the second and the fifth characters of the string "taarrrataa", and the new string "trararataa" will be an anti-palindrome, so the answer is $1$.