题目
难度：★☆☆☆☆
类型：字符串
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
注意
假设字符串的长度不会超过 1010。
示例
输入:
"abccccdd"
输出:
7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
解答
方案1：使用计数器
这道题与最长回文子串题不同，要简单很多，题目中所给出的字符串，更像一个字符的集合，我们无需考虑其出现的先后顺序，因此，我们可以仅仅根据每个字符出现的个数计算出题目中的结果。
如果字符串中所有字符均只出现过欧数次，那么组成回文串的最大长度和输入字符串相等；
对于任意一个字符，我们如果出现次数为偶数，那么我们就使用该字符所有的出现次数，如果是奇数，我们需要取不大于其出现次数的最大偶数；
如果字符串中存在字符出现过奇数次，那么组成回文串后，出现过奇数次的字符中多余的字符可以放在最中间，在原始结果的基础上加一，因此我们需要一个变量（odd_flag），探测是否有字符出现过奇数次；
from collections import Counter
class Solution:
def longestPalindrome(self, s: str) -> int:
counter = Counter(s) # 统计s中各个字符出现的次数
res, odd_flag = 0, 0 # 最终结果，出现基数次flag设置成为0
for k, v in counter.items(): # 对于每一条统计记录
res += (v // 2) * 2 # 加上该字符成对出现最大数量
if v % 2 == 1: # 只要有一个字符的出现次数是奇数
odd_flag = 1 # 最后结果就是要+1的
return res + odd_flag # 返回结果
这里有个列表版本计数器，道理类似：
class Solution:
def longestPalindrome(self, s: str) -> int:
counter = [0] * 58
for x in s:
counter[ord(x) - ord('A')] += 1
res, odd_flag = 0, 0
for n in counter:
if n % 2 == 1:
res += n - 1
odd_flag = 1
else:
res += n
return res + odd_flag
方法2：不用计数器
# 一对一对取出，如果是单着的，选一个就行
def longestPalindrome1_2(self, s):
s_list = list(s)
res, odd = 0, 0
while s_list:
c = s_list.pop() # 弹出最后一个元素
if c in s_list: # 最后一个元素出现在剩下的元素中
s_list.remove(c) # 删除相同的，相当于同时删除了一对
res += 2 # 长度加2
else:
odd = 1 # 选一个奇数的放中间
return res + odd
如有疑问或建议，欢迎评论区留言~
