题解：CF1582C Grandma Capa Knits a Scarf

题意

t

组数据。

给你一个包含

n

个字符的字符串

s

，你可以删除其中的一些字符，来使这个字符串回文。输出最少删除的字符个数。

分析

众所周知，字符串只有

26

个字符，我们完全可以暴力，然后双指针优化。如果说两个一样就跳过，因为这两个字符是回文的，否则我们就删除左指针指向的字符或者右指针指向的字符。当然，如果这两个指针指向的字符都不能被删去，那么这种方法就不行。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF=1e17+7;
int t,n;
string s;
signed main()
{
    cin>>t;
    while(t--){
        cin>>n>>s;
        s=" "+s;
        int ans=INF;
        for(int i='a';i<='z';i++){
            int l=1,r=n,flag=0,count=0;
            while(l<r){
                if(s[l]!=s[r]){
                    if(s[l]==i){
                        l++;
                        count++;
                    }else if(s[r]==i){
                        r--;
                        count++;
                    }else{
                        flag=1;
                        break;
                    }
                }else{
                    l++;
                    r--;
                }
            }
            if(!flag) 
				ans=min(ans,count);
        }
        if(ans==INF)
            cout<<"-1"<<endl;
        else
            cout<<ans<<endl;
    }
    return 0;
}

题解：CF1582C Grandma Capa Knits a Scarf

文章操作

题意

分析

代码

相关推荐

评论

题解：CF1582C Grandma Capa Knits a Scarf