409.最长回文串.md

题目描述：给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写，比如“Aa”不能当成一个回文字符串。

eg:

输入:
"abccccdd"

输出:
7

解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

思路描述：刚开始看错了题目，以为是求最长回文子串

class Solution {
public:
    string reverse1(string s){
        string temp = "";
        for(int i = s.size() - 1; i >= 0; i --)
            temp += s[i];
        return temp;
    }

    int longestPalindrome(string s) {
        int length = 0;
        for(int i = 2; i <= s.size(); i ++){
            for(int j = 0; j < s.size() - i; j ++){
                string subStr = s.substr(j, i);
                string temp = subStr;
                reverse(subStr.begin(), subStr.end());
                if(temp == subStr){
                    length = max(length, (int)subStr.size());
                    break;
                }
            }
        }
        return length;
    }
};

然后是发现是去构造回文串，那无非就是去统计一下每个字母的个数，分别除以2再乘以2相加就得出来了，这时候还用map，其中要注意的是最后要不要加1，比如dccaccd就要再加1，如果是dccccd就不需要了。

完美解决!

class Solution {
public:
    int longestPalindrome(string s) {
        int length = 0;
        bool isEven = true;
        unordered_map<char, int> smap;
        for(int i = 0; i < s.size(); i ++)
            smap[s[i]] ++;
        for(unordered_map<char, int>::iterator iter = smap.begin(); iter != smap.end(); iter ++){
            if(iter->second % 2 != 0) isEven = false;
            length += iter->second/2 * 2;
        }
        if(isEven) return length;
        return length + 1;
    }
};