题目描述

难度分:$1600$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的字符串$s$，只包含小写字母。

如果对于每个$1$到$n$的下标$i$，都满足$s[i] \neq s[n+1-i]$，那么称$s$为【反回文串】。

每次操作，你可以交换$s$中的任意两个字符。

最少操作多少次，可以使$s$是【反回文串】？

输出最小操作次数。如果无法做到，输出$-1$。

输入样例

10
10
codeforces
3
abc
10
taarrrataa
10
dcbdbdcccc
4
wwww
12
cabbaccabaac
10
aadaaaaddc
14
aacdaaaacadcdc
6
abccba
12
dcbcaebacccd

输出样例

0
-1
1
1
-1
3
-1
2
2
2

算法

贪心+分类讨论

首先可以过滤掉两种无解的情况：

1. 字符串$s$的长度为奇数，根据对反回文串的要求，中心字符一定做不到$s[i] \neq s[n+1-i]$。
2. 在字符串$s$的长度为偶数的情况下，某个字母的出现频率超过了$\frac{n}{2}$，那它一定也会分布在两翼，并且有一翼全部是它，满足不了$s[i] \neq s[n+1-i]$。

剩下的情况全部有解，设$counter[k]=(s[i]=s[n+1-i]=k)$的$i$数量（$i \leq \frac{n}{2}$）。此时优先对满足$s[i]=s[n+1-i]$的位置“内部消化”，如果有一对a和一对b对称，那么交换一个a和一个b就能破坏掉这两对。但是有可能满足$s[i]=s[n+1-i]$的位置$i$有奇数个，此时就找一个满足$s[i] \neq s[n+1-i]$的位置交换一下即可破坏掉最后这个落单的对称字母对，因为每个字母的出现次数都不会超过$\frac{n}{2}$。

但是如果某对$s[i]=s[n+1-i]=x$的字母出现得特别多，超过了所有满足$s[i]=s[n+1-i]$位置的一半。那就要用其他不同于$x$的字母来交换，会交换$counter[x]$次。

综上，最终的答案就是$max(max_{c=letter}^{z}counter[letter],\lceil \frac{\Sigma_{c=letter}^{z}counter[letter]}{2} \rceil)$（其中$\lceil . \rceil$表示对$.$向上取整）。

复杂度分析

时间复杂度

遍历了两遍字符串$s$，统计字母频数和满足$s[i]=s[n+1-i]$的位置数量，因此算法的时间复杂度为$O(n)$。

空间复杂度

除了输入的字符串，只开辟了长度为$26$的数组空间，用于统计频数，因此算法的额外空间复杂度为$O(\Sigma)$，其中$\Sigma$表示字符集大小，本题中$\Sigma=26$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <numeric>

using namespace std;
const int N = 200010;
int T, n, counter[26];
char s[N];

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        scanf("%s", s + 1);
        if(n&1) {
            puts("-1");
        }else {
            int maxfreq = 0;
            memset(counter, 0, sizeof(counter));
            for(int i = 1; i <= n; i++) {
                counter[s[i] - 'a']++;
                maxfreq = max(counter[s[i] - 'a'], maxfreq);
            }
            if(maxfreq > n/2) {
                puts("-1");
                continue;
            }
            memset(counter, 0, sizeof(counter));
            for(int i = 1; i <= n/2; i++) {
                if(s[i] == s[n + 1 - i]) {
                    counter[s[i] - 'a']++;
                }
            }
            int mx = 0, tot = 0;
            for(int i = 0; i < 26; i++) {
                mx = max(mx, counter[i]);
                tot += counter[i];
            }
            printf("%d\n", max(tot + 1>>1, mx));
        }
    }
    return 0;
}