LeetCode 题解工作台
最长回文串
给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的 回文串 的长度。 在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。 示例 1: 输入: s = "abccccdd" 输出: 7 解释: 我们可以构造的最长的回文串是"dccaccd", 它…
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 贪心·invariant
答案摘要
一个合法的回文字符串，最多存在一个出现奇数次数的字符，其余字符出现次数均为偶数。 因此，我们可以先遍历字符串 ，统计每个字符出现的次数，记录在数组或哈希表 中。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的 回文串 的长度。
在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。
示例 1:
输入:s = "abccccdd" 输出:7 解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
示例 2:
输入:s = "a" 输出:1 解释：可以构造的最长回文串是"a"，它的长度是 1。
提示:
1 <= s.length <= 2000s只由小写 和/或 大写英文字母组成
解题思路
方法一：计数
一个合法的回文字符串，最多存在一个出现奇数次数的字符，其余字符出现次数均为偶数。
因此，我们可以先遍历字符串 ，统计每个字符出现的次数，记录在数组或哈希表 中。
然后，我们遍历 ，对于每个次数 ，将 除以 2 取整，再乘以 2，累加到答案 中。
最后，如果答案小于字符串 的长度，则将答案加一，返回 。
时间复杂度 ，空间复杂度 。其中， 为字符串 的长度，而 为字符集大小，在本题中 。
class Solution:
def longestPalindrome(self, s: str) -> int:
cnt = Counter(s)
ans = sum(v // 2 * 2 for v in cnt.values())
ans += int(ans < len(s))
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Interviewer may ask why counting frequencies is sufficient for palindrome length.
- question_mark
They might check if you correctly handle case sensitivity and odd counts.
- question_mark
They may probe alternative approaches and ask why a full sort or permutation is unnecessary.
常见陷阱
外企场景- error
Forgetting that letters are case sensitive, mixing 'A' and 'a'.
- error
Failing to include a single odd-count character as the palindrome center.
- error
Attempting to build the actual palindrome string rather than just calculating its length, which wastes time.
进阶变体
外企场景- arrow_right_alt
Compute the longest palindrome substring instead of using all letters.
- arrow_right_alt
Allow the input string to include digits or special characters requiring extended hash handling.
- arrow_right_alt
Return one actual palindrome string rather than just its length.