题目描述

409. 最长回文串

思路

题目不难，就是所有的坑我都踩进去了。
"abccccdd" -> a: 1, b:1, d:2, c:4
我的思路是 偶数个数的直接相加，然后奇数里面选最大的就是答案：2+4+1=7.
但是有些样例过不了，看了别人的解释：

1. 如果某字母有偶数个，因为偶数有对称性，可以把它全部用来构造回文串；但如果是奇数个的话，并不是完全不可以用来构建，也不是只能选最长的那个，而是只要砍掉1个，剩下的变成偶数就可以全部计入了
2. 但奇数字母里，可以保留1个不砍，把它作为回文串的中心，所以最后还要再加回一个1
3. 但是！如果压根没有奇数的情况，这个1也不能随便加，所以还要分情况讨论。用了flag。

代码

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> m;
        for (char c : s) {
            m[c]++;
        }
        int res = 0;
        int single = 0;
        int flag = false;
        for (auto it = m.begin(); it != m.end(); it++) {
            if (it->second % 2 == 0) {
                res += it->second;
            } else {
                flag = true;
                res = res + it->second - 1;
            }
        }
        return flag ? res + 1 : res;

    }
};