题目:题目在这
分析:寻找能将字符串转变为回文的最小修改次数。
思路:
从a-z这些字母进行循环,依次取答案最小值即可。值得注意的是本题使用了双指针来对对应字母能否得到答案进行判断。
代码:
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define modulo 998244353
using namespace std;
int n;
string s;
int BRUTE(int idx){
int L=0,R=s.size()-1,Q=0;
while(L<=R){
if(s[L]!=s[R]){
if(s[L]-'a'==idx)
L++,Q++;
else if(s[R]-'a'==idx)
R--,Q++;
else
return INT_MAX;
}
else
L++,R--;
}
return Q;
}
int32_t main()
{
cin.tie(0),iostream::sync_with_stdio(0);
int testcases;
cin>>testcases;
while(testcases--){
cin>>n>>s;
int ANS=INT_MAX;
for(int i=0;i<26;i++)
ANS=min(BRUTE(i),ANS);
cout<<(ANS==INT_MAX?-1:ANS)<<endl;
}
}