当前位置: 代码迷 >> 综合 >> 好题分析:codeforce Round#750--C Grandma Capa Knits a Scarf
  详细解决方案

好题分析:codeforce Round#750--C Grandma Capa Knits a Scarf

热度:22   发布时间:2023-11-22 03:47:46.0

题目:题目在这

分析:寻找能将字符串转变为回文的最小修改次数。

思路:

从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;
}
}

  相关解决方案