LeetCode 最长回文串
文章目录最长回文串题目解题思路代码实现实现结果
最长回文串
作者："大梦三千秋
题目来源：https://leetcode-cn.com/problems/longest-palindrome/
题目给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。
示例 1:
输入:
"abccccdd"
输出:
7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
解题思路
回文串的概念：就是正反读都一样的字符串。例如：
abba，这个字符串是回文串，中心界限是 ab|ba 中间这条竖线的位置。abdba，而这个字符串也是回文串，中心界限在 ab(d)ba 中字符 d 的位置。
在这里我们可以看出，构成回文串，字符个数有可能是奇数，也有可能是偶数。
当构成回文串的字符个数为偶数的情况下，字符一定是成对出现的（如 abba，都是成对存在）；当构成回文串的字符个数为奇数的情况下，剔除中间中心的字符，其他的字符也是成对存在的。（如 abdba，剔除中心字符 d，其他字符也是成对）
但是这样需要注意的是，题中所给出的字符，当某个字符个数为奇数的情况下，并不是说不能用来构建回文串，只要剔除一个，变为偶数，那么同样可构成回文串。
当某个字符个数为奇数的情况下，可以保留其中 1 个不剔除，用以作为回文串中心，所以需要看情况在成对字符构成回文串后，将保留的这 1 个字符添加进去。若是字符都是成对的情况，则不需要考虑这种情况。
代码实现class Solution:
def longestPalindrome(self, s: str) -> int:
from collections import Counter
# 导入 Counter 类，用以统计字母出现的次数
d = Counter(s)
ans = len(s)
# 统计字母出现次数为奇数有多少
odd = 0
# 遍历字母对应的个数
for value in d.values():
# 统计字母出现次数为奇数有多少
# 先对符合条件的进行统计 + 1
if value % 2 != 0:
odd += 1
# 当 odd 为 0 的情况下
# 也就是所有字符都成对存在的情况下，直接返回题目所给字符的长度即可
# 若 odd 不为 0，也就是有出现字母个数为奇数的情况下，
# 这里的思路是将所有的字符都添加进来，字符出现次数为奇数的情况，进行统计
# 将这些情况全部剔除，但同时需要保留 1 个字符作为中心，所以最后要 + 1
return ans if odd == 0 else ans - odd + 1
实现结果
以上就是根据回文串的概念，左右对称构造字符串来解决《最长回文串》问题的主要内容。
欢迎关注微信公众号《书所集录》
作者："大梦三千秋
