[C++知识库]codeforces 1582 C. Grandma Capa Knits a Scarf

题意：在字符串中选择一个字符删除任意个，最后形成回文串；

题解：

回文串的特点是两两对称，那就双指针找到最外侧的两个不相同的，一定选择其中的一个删除才有可能构成回文串；然后就都算，取最小；

代码：

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		string s;
		cin >> s;
		char a, b;
		int l = 0, r = n - 1;
		int flag = 0;
		while (l<r)
		{
			if (s[l] != s[r])
			{
				flag = 1;
				a = s[l];
				b = s[r];
			/*	cout << l + 1 << " " << r + 1 << endl;
				cout << a << " " << b << endl;*/
				break;
			}
			else
			{
				l++;
				r--;
			}
		}
		if (flag == 0)
		{
			cout << 0 << endl;
		}
		else
		{
			int as1=0, as2 = 0;
			l = 0, r = n - 1;
			int k1 = 0, k2 = 0;
			while (l<r)
			{
				if (s[l] != s[r])
				{
				
					if (s[l] == a)
					{
						l++;
						as1++;
					}
					else if (s[r] == a)
					{
						r--;
						as1++;
					}
					else
					{
						k1++;
						break;
					}
				}
				else
				{
					l++;
					r--;
				}
			}
			l = 0, r = n - 1;
			while (l < r)
			{
				if (s[l] != s[r])
				{
				
					if (s[l] == b)
					{
						l++;
						as2++;
					}
					else if (s[r] == b)
					{
						r--;
						as2++;
					}
					else
					{
						k2++;
						break;
					}
				}
				else
				{
					l++;
					r--;
				}
			}
			if (k1&&k2)
			{
				cout << -1 << endl;
			}
			else
			{
				if (k1)
				{
					cout << as2 << endl;
				}
				else if (k2)
				{
					cout << as1 << endl;
				}
				else
				{
					cout << min(as1, as2) << endl;
				}
			}
		}
	}
}