容易证明一个长度为 的串 是“完美回文”，当且仅当 。下面给出证明：
（1）
首先 本身必须是回文的，那么就有 。然后 右移一个单位也必须回文，即 。
此时可以发现 串满足 即 串中任意两元素均相等。
（2）
和上面的证明方法基本相同，这里不再重复。
因此满足条件的串 必然满足 ，直接贪心的记录 个字母的出现次数，然后保留出现次数最多的字母即可，时间复杂度为 可以通过该题。
// #pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
using namespace std;
const int N = 1000010;
const int inf = 1e18;
const int mod = 998244353;
signed main()
{
cin.tie(0)->sync_with_stdio(false);
int T;
cin >> T;
while (T--)
{
string s;
cin >> s;
int buc[26] = {0};
for (char &i : s)
++buc[i - 'a'];
cout << s.size() - *max_element(buc, buc + 26) << '\n';
}
return 0;
}
喜欢的话，留下你的评论吧～