给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。
在构造过程中,请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。示例 1:
输入:
"abccccdd"输出:
7解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-palindrome
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
1.看懂题:题目是找到这些字母构造成的最长的回文串,也就是说:我们要拿题目给定我们的字符串中的字母去构造最长的的回文串。
如何理解回文串:
成中心堆成的串,无论在前面读还是在后面读,读出来的字符串都是一样的。有两种情况,一是最中间有一个字符,然后两边的字符都一样。然后还有一种情况就是没有中心这个字符串,把这个字符串劈成两半他们的字符是对称分布的。
一情况:abcdcba 二情况 :abccba
也就是说,我们需要把偶数个字符加入进来,如果有字符成奇数个把其中一个作为中心,但是只能取一个这样的字符。每一个字符ch,如果它出现了n次那么它加入的个数是n/2 *2,注意这个n/2取得是整数,也就是说n%2得部分是没有算进去的,然后如果加进去的字符个数是偶数,并且当前的字符数量%2仍然有余1,说明现在还没有加入那一个在中心的单个字符,那么我们就把它加上,其他情况都不必加了。
class Solution {
public:
int longestPalindrome(string s) {
unordered_map<char,int> count;
int ans = 0;
for(char c: s)
{
count[c]++;
}
for(auto p:count)
{
int v = p.second;
ans += v/2*2;
if((v%2)!=0 && (ans%2) ==0)
{
ans++;
}
}
return ans;
}
};