409. 最长回文串

解题思路

既然是求最长回文串，那么左右字符个数应该对称。对于偶数个字符来说，正好可以左右排列；而对于奇数个字符来说，除了左右排列需要的偶数个字符外，还要有一个中心点。注意，对于所有的奇数字符，回文串只需一个中心点就够了。如果左右对称字符个数之和小于原串长度，说明有奇数个字符，最后需要加上一个中心点；否则就全为偶数个字符。

代码

class Solution:
    def longestPalindrome(self, s: str) -> int:
        if not s:
            return 0
        dic = {}
        for i in s:
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
        countA = 0
        countB = 0
        # 记录中心点左右对称的字符个数
        for j in dic:
            if dic[j] % 2 == 0:
                countA += dic[j] # 偶数字符个数
            else:
                countB += dic[j]-1 # 奇数字符个数减去1个中心点
        # 有奇数个字符
        if countA+countB<len(s):
            return countA+countB+1
        # 全为偶数个字符
        else:
            return countA