LeetCode 409简单哈希表
最长回文串 图解题解
这道题到底在问什么
给定一个字符串 s（区分大小写），用它里面的字母拼一个回文串，返回能拼出的最长长度。
- 输入
- s = "abccccdd"
- 输出
- 7（如 dccaccd）
最优解：一步一步想明白
- 3思路一句话：先数每个字母频次，把成对的部分累加；有剩单的就给中心 +1。下面一步步演给你看。
- 4开始前：频次表是空的，答案长度 = 0。我们先把每个字母出现几次数清楚。
- 5指针走到下标 0，这一格的字母是 'a'。把它记进频次表。
- 6'a' 的次数加一，现在 cnt['a'] = 1。继续往后数。
- 7指针走到下标 1，这一格的字母是 'b'。把它记进频次表。
- 8'b' 的次数加一，现在 cnt['b'] = 1。继续往后数。
- 9指针走到下标 2，这一格的字母是 'c'。把它记进频次表。
- 10'c' 的次数加一，现在 cnt['c'] = 1。继续往后数。
- 11指针走到下标 3，这一格的字母是 'c'。把它记进频次表。
- 12'c' 的次数加一，现在 cnt['c'] = 2。继续往后数。
- 13指针走到下标 4，这一格的字母是 'c'。把它记进频次表。
- 14'c' 的次数加一，现在 cnt['c'] = 3。继续往后数。
- 15指针走到下标 5，这一格的字母是 'c'。把它记进频次表。
- 16'c' 的次数加一，现在 cnt['c'] = 4。继续往后数。
- 17指针走到下标 6，这一格的字母是 'd'。把它记进频次表。
- 18'd' 的次数加一，现在 cnt['d'] = 1。继续往后数。
- 19指针走到下标 7，这一格的字母是 'd'。把它记进频次表。
- 20'd' 的次数加一，现在 cnt['d'] = 2。继续往后数。
- 21数完了：'a' 出现 1 次，'b' 出现 1 次，'c' 出现 4 次，'d' 出现 2 次。接下来按字母看能凑几对。
- 22字母 'a' 只出现 1 次，凑不成对（红色），暂时贡献 0 个长度。它可能留给中心。
- 23'a' 出现奇数次，凑完对后还剩一个落单的（红色）。先记下：最后可以把它（或任意一个落单字母）放到回文正中心。
- 24字母 'b' 只出现 1 次，凑不成对（红色），暂时贡献 0 个长度。它可能留给中心。
- 25'b' 也是奇数次、又剩一个落单的。但回文中心只有一个位置，已经占了，所以这次不再加长。
- 26字母 'c' 出现 4 次，能凑出 2 对（绿色这些），左右对称各放一半，答案长度加 4，现在 = 4。
- 27字母 'd' 出现 2 次，能凑出 1 对（绿色这些），左右对称各放一半，答案长度加 2，现在 = 6。
- 28最后一步：因为有落单字母，把其中一个放到回文正中心，长度再 +1。最长回文串长度 = 7。
⚠️ 容易写错的地方
✗ 错：对每个奇数次字母都给中心 +1
✓ 对：无论几个奇数次字母，中心最多只 +1
回文中心只有一个位置，多个落单字母只能选一个放中心，其余浪费
✗ 错：用 c//2 后忘了再乘 2
✓ 对：成对贡献是 c//2*2，不是 c//2
c//2 是对数，每对占 2 个字符，长度要乘回 2
✗ 错：把奇数次字母的次数整段丢弃
✓ 对：奇数次也能用「次数−1」的偶数部分成对
如出现 5 次能凑 2 对贡献 4，只是多出的那 1 个落单
完整代码（Python / C++ / Java）
Python
def longestPalindrome(s):
from collections import Counter
cnt = Counter(s) # 数每个字母出现几次
ans = 0
odd = False # 是否存在奇数次字母
for c in cnt.values():
ans += c // 2 * 2 # 成对的部分贡献长度
if c % 2 == 1:
odd = True # 有落单字母
return ans + (1 if odd else 0) # 落单的放中心 +1C++
int longestPalindrome(string s){
int cnt[128] = {0};
for (char c : s) cnt[(int)c]++;
int ans = 0; bool odd = false;
for (int c : cnt) {
ans += c / 2 * 2;
if (c % 2 == 1) odd = true;
}
return ans + (odd ? 1 : 0);
}Java
public int longestPalindrome(String s) {
int[] cnt = new int[128];
for (char c : s.toCharArray()) cnt[c]++;
int ans = 0; boolean odd = false;
for (int c : cnt) {
ans += c / 2 * 2;
if (c % 2 == 1) odd = true;
}
return ans + (odd ? 1 : 0);
}复杂度
时间
O(n)
扫一遍字符串数频次，再扫一遍频次表，都是线性
空间
O(k)
频次表只存出现过的字母，字母集合大小有限（最多 128）
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最长回文串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么除了中心，其它字母都要成对？+
回文左右对称，位置 i 和它的镜像位置放的必须是同一个字母，所以每用一个就要在对称位再放一个，成对出现；只有正中心那个位置没有镜像，可以单独放一个。
如果字符串为空会怎样？+
频次表为空，ans=0，也没有奇数次字母，返回 0。
能不能不用计数表？+
可以用集合：遍历时字母在集合里就配成一对、长度+2 并移除，不在就加入；最后集合非空说明有落单字母、中心+1。本质一样，都是判断每个字母的奇偶。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 最长回文串 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。