[C++知识库]Codeforces Round #750 (Div. 2) C. Grandma Capa Knits a Scarf（本题解图文结合，理解更简单）

Codeforces Round #750 (Div. 2)的其他题解点我

C. Grandma Capa Knits a Scarf

题目大意：
给出一个字符串，你可以删除若干个相同字符，问最少删除多少个字符可以使字符串变成一个回文串

思路：
首先我们从外往里找，找出第一个不相等的字符


如果要想通过删除变成回文串，那么删除的必然是这两个字符之一
所以我们继续往里枚举两种情况（上图是删b，和删c）
如果相同就跳过，不相同就删除我们可以删除的那个字符，如果删除不了该种情况就不行，如果两种情况都不行，那么就是-1了

AC代码：

#include <bits/stdc++.h>
#define PII pair<int,int>
#define ll long long

using namespace std;

const double eps = 1e-8;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int INF = 1<<30;
inline void swap(int &x, int &y){x^=y^=x^=y;}
inline int gcd(int a,int b) {return !b ? a : gcd(b,a%b);}
int main(){	
    int T;
    scanf("%d", &T);
    while(T--){
        int n;
        scanf("%d", &n);
        string x;
        cin >> x;
        int len = x.length();
        int ans1 = 0, ans2 = 0;
        int L = 0, R = len - 1;
        while(L <= R && x[L] == x[R]){L++,R--;}
        if(L > R)printf("0\n");
        else {
            char a = x[L];
            int l = L, r = R;
            while(l <= r){
                if(x[l] == x[r])l++,r--;
                else if(x[l] == a)ans1++, l++;
                else if(x[r] == a)ans1++, r--;
                else {
                    ans1 = n + 1;
                    break;
                }
            }
            char b = x[R];
            l = L, r = R;
            while(l <= r){
                if(x[l] == x[r])l++,r--;
                else if(x[l] == b)ans2++, l++;
                else if(x[r] == b)ans2++, r--;
                else {
                    ans2 = n + 1;
                    break;
                }
            }
            int ans = min(ans1, ans2);
            if(ans1 == n + 1 && ans2 == n + 1)ans = -1;
            printf("%d\n", ans);
        }
    }

    return 0;
}