題目描述

409. 最長回文串

思路

題目不難，就是所有的坑我都踩進去了。
"abccccdd" -> a: 1, b:1, d:2, c:4
我的思路是 偶數(shù)個數(shù)的直接相加，然后奇數(shù)里面選最大的就是答案：2+4+1=7.
但是有些樣例過不了，看了別人的解釋：

1. 如果某字母有偶數(shù)個，因為偶數(shù)有對稱性，可以把它全部用來構造回文串；但如果是奇數(shù)個的話，并不是完全不可以用來構建，也不是只能選最長的那個，而是只要砍掉1個，剩下的變成偶數(shù)就可以全部計入了
2. 但奇數(shù)字母里，可以保留1個不砍，把它作為回文串的中心，所以最后還要再加回一個1
3. 但是！如果壓根沒有奇數(shù)的情況，這個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;

    }
};