Longest Palindrome
你会得到一个由大写和小写字母组成的字符串 s。重新排列其中的字母，构造出尽可能长的回文，并返回该回文的长度。你可以按任意顺序排列字母，也可以舍弃一些字母，但每个字母的使用次数不能超过它在 s 中出现的次数。
大写字母和小写字母是不同的字母，所以 Aa 不是回文。
函数
- sstring
- 你可以使用的字母，包括大写和小写
- 返回值integer
- 你可以用这些字母构建的最长回文的长度
约束条件
1 ≤ s.length ≤ 5 × 104s只包含英文字母，即a到z和A到Z。- 你不必使用每个字母。
示例
- 输入
- s = "coddyCode"
- 输出
- 5
- 解释
o出现了两次，d出现了三次，其余字母各出现一次。一对o、一对d，再加上中间剩下的一个字母，长度为 5，例如doCod。
- 输入
- s = "Aa"
- 输出
- 1
- 解释
A和a是不同的字母，因此不存在这样的配对。单个字母本身就是长度为 1 的回文。
- 输入
- s = "xxxyyy"
- 输出
- 5
- 解释
- 两个
x和两个y配成对，剩下的一个字母放在中间，例如xyxyx。最后一个y没有搭档，因此不放进去。
进阶
你能否仍在 O(n) 时间内，返回一个最长回文串本身及其长度？
提示
逐个打开提示，每个都会多透露一点。
回文从两端读起来都一样。将第一个字母与最后一个字母匹配，第二个字母与倒数第二个字母匹配，以此类推。这说明它包含的每个字母分别有多少个？
除了可能恰好位于中间的那个字母外，每个字母都会成对出现。因此，
s的顺序完全不重要，重要的只是每个字母出现的次数。统计每个字母的数量。每个数量中最大的偶数部分都可以组成字母对，因此把每个数量向下取整到偶数后相加。如果有任何数量是奇数，就可以把一个剩余字母放在中间：只加 1 次。
题解
由于你可以重新排列，s 的顺序并不重要，重要的是每个字母出现的次数。回文中，每个字母在另一侧都有一个对应的副本，只有中间位置最多可以有一个字母。因此，统计各字母的数量，保留所有成对的字母，如果有剩余字母，就在中间加上一个。
对相邻项进行排序和配对
思路
排序会把相同的字母放在一起，因此每一对字母都相邻。在 xxxyyy 中，索引 0 和 1 处的 x 相同：取出这一对，然后向前移动两位。索引 2 处的 x 和 y 不同，因此这个 x 没有配对，你只需移动一位。索引 3 和 4 处的 y 组成第二对，最后一个 y 则单独剩下。两对得到 4，再加上中间的一个字母：5。
当配对使用的字母少于全部 n 个字母时，就会有字母剩下，因此不需要单独设置标记。排序的时间开销为 O(n log n)，排序后的副本占用 O(n) 空间。
算法
- 对
s中的字母排序。 - 用索引
i遍历排好序的字母。如果i和i+1处的字母相同，就将长度加 2，并向后移动两位；否则向后移动一位。 - 如果长度小于字母数量，就为中间的字母加 1。
- 返回长度。
def longestPalindrome(s):
letters = sorted(s)
n = len(letters)
length = 0
i = 0
while i + 1 < n:
if letters[i] == letters[i + 1]:
length += 2 # a pair: one copy on each side of the middle
i += 2
else:
i += 1
# A letter left without a partner can stand alone in the middle
if length < n:
length += 1
return length统计每个字母
思路
计数无需排序也能得到相同的信息。为每个字符代码保留一个计数器，一共 128 个，这样 A 和 a 会落在不同的计数器中。某个字母出现 c 次，就能提供向下取整到偶数的 c 个字母。
对于 coddyCode，o 和 d 各自组成的配对总共提供 4 个字母。还剩下 5 个字母未配对，其中任意一个都可以放在中间：5。第二个未配对的字母无法找到镜像。
遍历一次 s 填充计数器，再遍历一次 128 个计数器累加配对：时间复杂度为 O(n)，额外空间复杂度为 O(1)（在 R 中为 O(n)，因为首先会将 s 转换为代码向量）。
算法
- 创建 128 个初始值为 0 的计数器，并将
s中每个字母对应的计数器加 1。 - 对每个计数器，将向下取整到偶数的计数加到长度上。
- 如果长度小于
s的长度，说明某些计数是奇数，因此为中间字母加 1。 - 返回长度。
def longestPalindrome(s):
counts = [0] * 128 # one counter per character code, so 'A' and 'a' differ
for ch in s:
counts[ord(ch)] += 1
length = 0
for count in counts:
length += count // 2 * 2 # every pair fits, one copy on each side
# Fewer letters used than s has: some count is odd, so one letter can go in the middle
if length < len(s):
length += 1
return length
易错点和边界情况
- 完全丢弃奇数次计数。出现 3 次的字母仍然可以提供一对：
xxxyyy的结果是 5，而不是 1。 - 每遇到一个奇数次计数就加 1。只有一个字母能放在中间，所以
xxxyyy的结果是 5，而不是 6。 - 把
A和a当作同一个字母。Aa没有成对的字母，所以答案是 1，而不是 2。 - 只为
a到z设置计数器。大写字母的编码是 65 到 90，超出了这个范围；应根据完整的字符编码建立索引。
常见问题3
最长回文与最长回文子串有什么区别？
在这里，你可以重新排列字母，所以只需关注字母的数量，计数就能在 O(n) 时间内解决问题。最长回文子串要求回文已经作为一段连续的字母出现，需要使用另一种方法，例如从每个中心向两边扩展。对于 abab，这个问题的答案是 4（abba），子串版本的答案是 3（aba）。
最长回文的时间复杂度是多少？
使用计数法需要 O(n) 时间：每个字母都会让一个计数器加 1，无论 s 的长度是多少，把配对数相加都需要读取 128 个计数器。空间复杂度为 O(1)。排序并将相邻项配对需要 O(n log n) 时间和 O(n) 空间。
你必须使用 s 中的每个字母吗？
不。每一对字母都可以放进去，最多再把一个未配对的字母放在中间。因此，如果出现奇数次的字母最多有一个，答案就是 s 的长度；否则，答案就是 s 的长度减去出现奇数次的字母数量，再加 1。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def longestPalindrome(s):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "coddyCode"
预期输出
5