LeetCode 409简单哈希表
最长回文串 图解题解
这道题到底在问什么
给定一个包含大写字母和小写字母的字符串 s，返回通过这些字母构造成的最长回文串的长度。构造过程中区分大小写，比如 "Aa" 不能当作一个回文字符串。
- 输入
- s = "abccccdd"
- 输出
- 7
- 解释
- 可以构造 "dccaccd"，长度为 7。
- 输入
- s = "a"
- 输出
- 1
最优解：一步一步想明白
- 3这个想法完全正确。我们可以换一种更动态的写法：边扫描边把字符凑成一对。
- 4扫描结束后，length 是已经配成左右两边的长度；如果 odd 非空，就拿其中任意一个字符放中心，答案再加 1。
- 5odd = set(); length = 0odd 里放暂时没有配对成功的字符。length 只统计已经能放到回文两边的成对字符。
- 6odd.add(ch)单独一个 a 暂时不能放到两边，只能先作为“可能的中心”候选留在 odd 里。
- 7odd.add(ch)现在 odd={a,b}，表示 a 和 b 都还没找到第二个相同字符。
- 8odd.add(ch)第一个 c 也先放进 odd。
- 9if ch in odd: odd.remove(ch); length += 2高亮的两个 c 是刚凑成的一对，可以分别放在回文串左右两侧，所以 length 从 0 加到 2，c 从 odd 中移除。
- 10odd.add(ch)字符出现次数的奇偶性在切换：第 3 个 c 让 c 再次变成未配对状态。
- 11if ch in odd: odd.remove(ch); length += 2高亮的两个 c 是第二对 c。四个 c 一共能贡献 4 个位置，全部放到回文串两边。
- 12odd.add(ch)第一个 d 还不能单独贡献两边的位置，先进入 odd 等待配对。
- 13if ch in odd: odd.remove(ch); length += 2高亮的两个 d 是第三对。它们贡献 2 个位置，现在已经配成的长度是 6，odd 里还剩 a 和 b。
- 14return length + (1 if odd else 0)回文串最多只能有一个中心字符。odd 里虽然有 a 和 b 两个未配对字符，也只能任取一个放中心，最终答案是 7。
- 15这一步只是帮你确认答案为什么是 7；真正代码仍然只维护 odd 和 length。
- 18这题不需要真的拼出回文串。只要算出最多能放多少字符即可。
⚠️ 容易写错的地方
✗ 错：把所有奇数字符都加 1
✓ 对：最多只加 1 个中心字符
回文串只有一个中心位置。
✗ 错：把 "Aa" 当成一对
✓ 对：区分大小写，A 和 a 不同
题目明确大小写敏感。
✗ 错：尝试排序后构造字符串
✓ 对：只计算长度，不需要构造
题目返回长度，奇偶计数足够。
完整代码（Python）
Python
class Solution:
def longestPalindrome(self, s):
odd = set()
length = 0
for ch in s:
if ch in odd:
odd.remove(ch)
length += 2
else:
odd.add(ch)
return length + (1 if odd else 0)复杂度
时间复杂度
O(n)
每个字符扫描一次，集合操作平均 O(1)。
空间复杂度
O(1)
英文字母大小写字符集有限，odd 大小有常数上界。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最长回文串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「哈希表」，换最直接的暴力解会差在哪？+
哈希表抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。