手撕LeetCode #409——Python

409. 最长回文串

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
示例：

输入：“abcccdd”
输出：“7”
解释：可以构造的最长回文串是“dccaccd”，长度是7

解题思路：
只要是出现次数为偶数的字符，直接加上它的出现次数；出现次数为奇数的字符，加上它的出现次数减1（保持回文串的对称性）。如果有奇数出现的话，最后结果再加上1，因为回文串允许最中间的字符串为奇数个。

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        res = odd = 0
        cnt = collections.Counter(s)
        for v in cnt:
            res += cnt[v]
            if cnt[v] % 2 == 1:
                res -= 1
                odd += 1
        return res + (odd > 0)