LeetCode 409—— 最长回文串

1. 题目

2. 解题思路

要想组成回文串，那么只有最中间的字符可以是奇数个，其余字符都必须是偶数个。

所以，我们先遍历一遍字符串，统计出每个字符出现的次数。

然后如果某个字符出现了偶数次，那么回文串长度就增加这个字符出现的次数；如果某个字符出现了奇数次，那么回文串长度也只能增加小于这个奇数次的最大偶数。

最后，如果存在奇数个的字符，那么中间可以放一个奇数字符，回文串长度加 1。

3. 代码实现

class Solution {
public:
    int longestPalindrome(string s) {
        vector<int> alphabet_num(54, 0);
        for (size_t i = 0; i < s.size(); ++i) {
            int idx = 0;
            if (s[i] >= 'a' && s[i] <= 'z') {
                idx = s[i] - 'a';
            } else if (s[i] >= 'A' && s[i] <= 'Z') {
                idx = s[i] - 'A' + 26;
            }
            alphabet_num[idx]++;
        }
        int ret = 0;
        bool has_odd = false;
        for (size_t i = 0; i < alphabet_num.size(); ++i) {
            ret += (alphabet_num[i] / 2) * 2;
            if (alphabet_num[i] % 2 != 0) {
                has_odd = true;
            }
        }
        if (has_odd) {
            ret += 1;
        }
        return ret;
    }
};