给出一个包含大小写字母的字符串。求出由这些字母构成的最长的回文串的长度是多少。
数据是大小写敏感的,也就是说,"Aa" 并不会被认为是一个回文串。
样例
给出 s = "abccccdd" 返回 7
一种可以构建出来的最长回文串方案是 "dccaccd"。
这个题我踩了一个大坑,我先说我一开始想的思路啊,是这样的:要够成回文串除了最中间可以是奇数个相同的字母以外,两边的都必须是对称的,那么我用map统计每个字母出现的次数,然后出现偶数次的都可以加到回文串中,出现奇数个的我把奇数最大的那个加入回文串中,这样就可以得到需要的数目了啊。这样做的代码如下:
int longestPalindrome(string s) {
int res=0;
int ji=0;
map<char,int> num_of_letter;
for(auto ss:s)
{
num_of_letter[ss]++; //统计每个字符出现的个数
}
for(auto num:num_of_letter)
{
if(num.second%2==0) //如果这个字母是偶数个,肯定全部能放到回文串中
{
res+=num.second;
}
else //最后我们加上最大的奇数个数,放在最中间就可以了。
{
if(num.second>ji)
ji=num.second;
}
}
return res+ji;
// write your code here
}
测试的时候一半的数据都通过了,但是还是出现了问题,我一开始也想不通为什么,甚至我把每个字母和次数都打印出来也没有看出端倪,于是和振哥交流了一下,我去泡了袋面吃,然后振哥说发现为什么了,知道原因之后只能说自己陷入自己挖的坑里了。
错误的原因是这样的,虽然说奇数个字母是不能放入回文串的,但是并没有人规定说是我必须把这奇数个都放进去,如果一个字母有5个的话我还是可以放4个进去啊。这样一想就知道错在哪里了,在原程序上要进行一些改动,着重要考虑两种情况,并不是简单的把奇数统计那里改一下就行了。
1:考虑全偶的情况。
2:考虑只有一个奇数个字母的情况,这样就要全部放进去
改了之后的代码如下:测试数据可以全部通过
int longestPalindrome(string s) {
if(s.size()==0)
return 0;
int res_ou=0;
int res_ji=0;
int ji=0;
map<char,int> num_of_letter;
for(auto ss:s)
{
num_of_letter[ss]++; //统计每个字符出现的个数
}
for(auto num:num_of_letter)
{
if(num.second%2==0) //如果这个字母是偶数个,肯定全部能放到回文串中
{
res_ou+=num.second;
}
else //最后我们加上最大的奇数个数,放在最中间就可以了。
{
ji++; //还要统计下是否真的有奇数,最后决定是否要加1和加奇数
res_ji+=num.second; //把奇数个的字母个数也加起来,最后减去个数就可以。
}
}
if(ji==0)
return res_ou;
else
return res_ou+res_ji-ji+1;
// write your code here
}