[LeetCode 409] Longest Palindrome

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note:

Assume the length of given string will not exceed 1,010.

Example:

Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

Diffculty Easy

Similar Problems [LeetCode 266] Palindrome Permutation Easy

Analysis

题意是给出一个字符串，用这个字符串中的字符来组成回文（区分大小写），求其能组成的最长回文字符串的长度。

思路一 扫描一遍给出的字符串，统计每个字符出现的个数。然后遍历一遍各个字符的个数， 对于每个字符的个数来说，有两种情况：

• 如果个数是偶数，则直接添加到长度中；
• 如果个数是奇数，则添加个数减 1 到长度中并且标记存在中心字符，

由于只有偶数数量的字符才能分配到回文字符串的两端，而中心可以是单个字符，最后直接返回长度即可。

优化：如果有奇数个字符，标记存在中心字符，然后直接取出这些字符数量的最大偶数，然后最后结果加 1 即可

思路二 可以换一种思路，只需找出有奇数个数的字符，我们采用的方法是使用一个 set 集合，如果遍历到的字符不在 set 中，那么就将其加入 set，如果已经在 set 里了，就将其从 set 中删去，这样遍历完成后 set 中就是所有出现个数是奇数个的字符了，那么我们最后只要用 s 的长度减去 0 和 set 长度减一之间的较大值即可，为啥这样呢，我们想，如果没有出现个数是奇数个的字符，那么 t 的长度就是 0，减 1 成了 -1 ，那么 s 的长度只要减去 0 即可；如果有奇数个的字符，那么字符个数减 1 ，就是不能组成回文串的字符，因为回文串最多允许一个不成对出现的字符。

思路三 这种方法利用到了 STL 中的count函数，就是找字符串中某个字符出现的个数，那么我们和 1 相与，就可以知道该个数是奇数还是偶数了，返回的写法和思路二相同

Solutions

解法一

class Solution {
public:
    int longestPalindrome(string s) {
        int letters[52] = {0};
        int plength = 0;
        bool hasCenter = false;

        for (auto c: s)
            isupper(c) ? letters[c - 'A' + 26]++ : letters[c - 'a']++;

        for (int i = 0; i < 52; i++) {
            if (letters[i] % 2) {           // 奇数
                plength += letters[i] - 1;
                hasCenter = true;
            } else {                        // 偶数
                plength += letters[i];
            }
        }

        return plength + hasCenter;
    }
};

优化

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

解法二

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_set<char> t;
        for (char c : s) {
            if (t.count(c) == 0) t.insert(c);
            else t.erase(c);
        }
        return s.size() - max(0, (int)t.size() - 1);
    }
};

解法三

class Solution {
public:
    int longestPalindrome(string s) {
        int odds = 0;
        for (char c = 'A'; c <= 'z'; ++c) {
            odds += count(s.begin(), s.end(), c) & 1;
        }
        return s.size() - max(0, odds - 1);
    }
};