4.25LongestPalindrome - WisperDin/blog GitHub Wiki

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note: Assume the length of given string will not exceed 1,010.

Example:

Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

找到由input字符构成的最长回文字符串的长度

首先，思考回文字符串的准确定义：

一个字符串从左到右和从右到左 遍历字符产生的字符串一样

再给出易于实现的定义：

回文字符串分两种：1. 偶数个字符的 （bffb），2. 奇数个字符的 (efgfe)

其中偶数个字符的包含偶数个字符对，(bffb :: b,f 两个字符对)

奇数个字符的包含偶数个字符对+一个字符 （efgfe :: e,f两个字符对+一个字符）（c :: 0个字符对+一个字符）

再考虑要由input字符串构成最长的字符串，则需要知道input字符串中

• 字符对的对数 设为 A
• 是否存在字符出现奇数次（因为奇数个的字符必定可以拆一个字符来构成回文串中心位置的字符） 设为B

所以最大回文串长度 = A + (B?1:0)

具体实现时，利用hashmap统计每个字符出现的次数（其实用数组也可以），每当有字符出现次数达到偶数次时，字符对对数计数器++,

遍历完字符串后，再遍历hashmap，查看有没有奇数次字符出现过

class Solution {
public:
    int longestPalindrome(string s) {
        int n = s.size();
        if (n==0)
            return 0;
        unordered_map<int,int> hashmap;
        int ans=0;
        int cCode;
        for(int i=0;i<n;i++){
            cCode = int(s[i]);
            hashmap[cCode]=hashmap[cCode]+1;
            int t = hashmap[cCode];
            if(t%2==0){
                ans++;
            }
        }
        
        bool existOdd=false;
        for(auto it = hashmap.begin();it!=hashmap.end();++it){
            if(it->second%2!=0){
                existOdd = true;
                break;
            }
        }
        ans=existOdd?ans*2+1:ans*2;
        return ans;
    }
};