409. 最长回文串 Longest Palindrome
Table of Contents
一、中文版
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。
示例 1:
输入:
"abccccdd"
输出:
7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
二、英文版
Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters. This is case sensitive, for example "Aa" is not considered a palindrome here. Note: Assume the length of given string will not exceed 1,010. Example: Input: "abccccdd" Output: 7 Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.
三、My answer
class Solution: def longestPalindrome(self, s: str) -> int: if not s: return 0 flag, res = 0, 0 counter = collections.Counter(s) for key in counter: if counter[key] % 2 == 0: res += counter[key] else: flag = 1 res += counter[key]-1 return res if flag == 0 else res + 1
四、解题报告
使用 collections.Counter() 生成类似字典的结构，存储字符串中字母出现的个数。
如果是偶数个直接放入 res 结果中；如果是奇数个，先把 奇数-1 存入结果，再利用 flag 标志位，如果 flag = 1 证明有奇数，再加上这个奇数位于中间位置。
注意不能直接加上最长的奇数位，特殊情况：abbbccc，则结果是 cbbbc，直接加上最长的奇数，会漏掉可以加上 cc 的情况，造成错误。
