【leetcode】409. Longest Palindrome

发表于

描述
给一个字符串，然后你重新组合，求组成回文数的最大字符数目。

思路
利用map数据结构保存每个字符出现的次数，显然偶数可以直接加2。为奇数的话，需要判断这个奇数是否大于1，大于1的话需要加上cnt(奇数)-1。又因为奇数可以放在中间，所以有奇数的话可以在最终的结果上再加上1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int longestPalindrome(string s) {
        map<char, int> chmap;
        for (auto ch : s) {
            chmap[ch]++;
        }
        int sum = 0;
        bool single = false;
        for (auto iter : chmap) {
            if (iter.second & 1) {
                single = true;
                sum += iter.second - 1;
            }
            else {    sum += iter.second;    }
        }
        if (single) { sum++; }
        return sum;
    }
};

参考资料
题目链接