LeetCode 409. 最长回文串（Longest Palindrome）

问题描述：

给定一个包含大写字母和 小写字母 的 字符串 ，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。

注：假设字符串的长度不会超过 1010。

示例：

C语言实现：

这里的回文是指：一个字符串和它的反转字符是相同的。

那么很明显这种字符串一定是关于中间左右对称的。

因此我们很容易推断出这种回文字符串存在三种形式，如上图：

• 字符串长度为0。
• 字符串长度是偶数，那么每种字符都存在偶数个。
• 字符串长度是奇数，除了最中间的 那种 字符出现奇数次以外，其他字符都必须出现偶数次。

因此对字符串s来说，要构成的最大的回文字符串，应该满足：

1. 所有出现偶数次的字符都可以全部添加到回文字符串中，
2. 如果存在出现奇数次的字符，那么次数最大的那个可以作为回文字符串中的中间字符。
3. 如果还存在其他的出现奇数次字符，假设它长度是n，那么它不能全部添加到回文字符串中，但是可以添加n-1个字符进去，因为n-1是偶数。

我们可以将第二条和第三条放在一起表述：

如果存在n个出现次数为奇数次的字符，其中C1,C2…Cn表示每个字符出现的次数，那么可以有S(odds) = (C1-1)+(C2-1)+…+(Cn-1) + 1 = C1+C2+…+Cn-n+1个字符可以添加到回文字符串中。

我们再将第一条加进来：

如果存在m个出现次数为偶数次的字符，其中E1,E2…En表示每个字符出现的次数，那么可以有S(evens) = E1+E2+…+En = (E1-0)+(E2-0)+…+(En-0) + 0 个字符可以添加到回文字符串中。

则，构成的最大的回文字符串长度Len(P) = S(odds) + S(evens)

注意加粗的部分，表明S(odds) 和 S(evens)可以用相同的表达式表示 ，不同的是每个元素减去的数不同，奇数时减1，偶数时减0，以及末尾加的数不同，奇数时加1，偶数时加0。

所以最终可以写出如下代码：

Java语言的实现：

Java 的实现和C语言的实现一致，不再撰述。

代码如下：

python语言的实现：

python 的实现和C语言的实现一致，不再撰述。

代码如下：