传智杯 第六届-复赛-第二场-B

题目描述：

        小红拿到了一个字符串，她可以操作最多1次：修改任意一个字符。小红希望操作结束后，长度为3的回文连续子串的数量尽可能多。请你求出这个数量。

输入描述:

        一个仅包含小写字母的字符串。长度不超过100。

输出描述:

        一个整数，代表操作结束后，长度为3的回文连续子串的数量的最大值。

示例1

输入：

abcde

输出:

1

说明:

将第二个字符修改为'd'即可，这样字符串变成"adcde"，共包含1个长度为3的回文子串。

解题思路：

        由于字符串的长度很小，可以直接依次更改每个字符，分别更改为上上个字符和下下个字符，然后分别判断每次更改后可以组成多少个回文子串。

注意：

        ①更改后需要对更改的字符复原，才能进行下一次更改。

代码：

#include<iostream>
#include<string>
#include<math.h>
#define int long long
using namespace std;

//查找
int find(string str)
{
	int count = 0;
	for (int i = 0;i < str.length() - 2;i++)
	{
		if (str[i] == str[i + 2])
		{
			count++;
		}
	}
	return count;
}

signed  main()
{
	//输入
	string str;
	getline(cin, str);

	int ma = 0;    //记录最大的回文子串数
	//依次字符、查找
	for (int i = 0;i < str.length();i++)
	{
		//有前面的字符
		if (i > 1)
		{
			char temp = str[i];   
			str[i] = str[i - 2];   //更改
			ma = max(ma, find(str));
			str[i] = temp;   //恢复
		}

		//有后面的字符
		if (i < str.length() - 2)
		{
			char temp = str[i];
			str[i] = str[i + 2];   //更改
			ma = max(ma, find(str));
			str[i] = temp;   //恢复
		}
	}
	cout << ma << endl;

	system("pause");
}