“最长回文串”这道题我最早是在准备面试刷题时遇到的。LeetCode 409 这道题题目本身不长但它在字符串处理和计数统计上非常典型几乎所有大厂笔试和面试题库里都有它的身影。这道题的核心价值在于它不需要你用多复杂的算法却能考察你对“回文串结构”的理解深度、对计数统计工具的选择能力以及能不能用最简代码把逻辑表达清楚。我见过不少人在这道题上写出冗长的双指针方案其实完全跑偏了。这篇文章我会从题目拆解到多语言实现再到容易踩的坑完整地过一遍希望能帮你彻底拿下它。1. 题目理解与核心思路拆解1.1 这道题到底在问什么先把原题翻译成人话给你一个字符串 s里面的字符可以随便打乱顺序重新排列你需要用这些字符拼出一个回文串返回这个回文串能达到的最长长度。注意不是让你输出这个回文串本身只问长度。举个例子s “abccccdd”。你可以重新排列成 “dccaccd”长度是 7这就是能拼出的最长回文串。为什么不是 8因为总共有 8 个字符但 ‘a’ 和 ‘b’ 各只出现 1 次你最多只能把其中一个放在正中间另一个就剩下了。一个很常见的错误理解是认为要“找出”字符串里已有的最长回文子串。那是另一道题LeetCode 5。这道题是“用给定的字符去构造”字符顺序无所谓本质是个计数题。一旦把这个区别搞清楚思路就顺了。1.2 回文串的结构决定了算法方向回文串长什么样左右对称比如 “racecar” 或者 “abcba”。从结构上看可以分为两半加一个中间点。左右两半是镜像关系所以每一个出现在左半的字符必须有一个相同的字符出现在右半。换句话说除了最中间可以放一个“落单”的字符之外其他所有字符都必须成对出现。这里就引出了这道题最核心的贪心判断某个字符出现了偶数次那它所有字符都可以用上左右各放一半。某个字符出现了奇数次那我们最多只能用到“它最大的偶数部分”比如出现 5 次最多用 4 次左右各 2 次。所有字符的偶数部分加起来如果还有某个字符剩下 1 次没用那剩下那 1 次可以放在正中间让总长度再多 1。1.3 从“计数”到“贪心”的推理链条整个解题思维是一条非常清晰的线。首先我们要知道每个字符出现了几次这需要做一次频率统计。然后对于每个频率值我们需要做“截断到最大偶数”的操作这在编程里对应的就是count // 2 * 2或者count - (count % 2)。最后判断整条字符串里是否存在奇数频率的字符如果存在最终答案加 1。很多题解把这段逻辑浓缩成了几行代码但真正面试的时候你需要把这条推理链当面讲清楚。我习惯这样表达先把所有能成对的字符都拿进来这是回文串的主体再看有没有单个字符能当“中心点”有就加一。这个说法直观面试官也容易跟上你的思路。2. 解法原理与计数方案选型2.1 哈希表统计与数组统计的取舍既然要先统计字符频率就面临一个工具选择的问题用哈希表HashMap/Counter还是用定长数组在 Python 里collections.Counter写起来非常舒服from collections import Counter class Solution: def longestPalindrome(self, s: str) - int: count Counter(s) ans 0 has_odd False for v in count.values(): ans v // 2 * 2 if v % 2 1: has_odd True return ans (1 if has_odd else 0)但有的面试官会追问一句这里能用数组替代哈希表吗能。因为这道题的字符集是有限的——如果是英文字母ASCII 范围只有 128 个或者只看大小写字母的话范围是A到z区间长度 58。用数组的索引代表字符的 ASCII 码值代表出现次数空间上比哈希表更省而且遍历速度更快因为数组的随机访问不需要计算哈希值。我用 Java 写的时候通常会直接用int[128]class Solution { public int longestPalindrome(String s) { int[] cnt new int[128]; for (char c : s.toCharArray()) { cnt[c]; } int ans 0; boolean hasOdd false; for (int v : cnt) { ans (v / 2) * 2; if (v % 2 1) { hasOdd true; } } return hasOdd ? ans 1 : ans; } }2.2 关于“边界字符集”的细节坑这里有一个隐藏的细节需要注意。ASCII 码表里A是 65z是 122中间连续区间长度是 58。所以有的题解会用int[58]并写cnt[c - A]这样更省内存。但也有题目可能包含小写字母以外的字符比如空格、数字甚至 Unicode 字符。一旦字符范围不确定int[128]可能不够用严格来说应该用int[256]单字节字符全覆盖或者干脆回到哈希表。我在实际做题时会先看一眼题目给的约束条件。LeetCode 409 的约束是字符串只包含大小写字母所以int[128]和int[58]都是安全的选择。但作为面试答题我会顺手说一句“这里用数组是因为字符集有限如果字符集不确定我会改用哈希表”这句话能体现出你对边界条件的敏感度。2.3 位运算技巧让代码更优雅除了v // 2 * 2这种写法还有一个在评论区经常看到的位运算写法能省一行逻辑ans v ~1。原理是任何整数在二进制下最低位如果是 1 就表示它是奇数如果是 0 就是偶数。v ~1的含义是“把最低位置 0”效果等同于“减去 1 如果是奇数的话”也就是把奇数变成比它小 1 的偶数。比如 5 的二进制是101~1是...11111110两者按位与得到100也就是 4。这样写代码可以稍微精简一点但可读性对初学者不太友好。我在平时分享时还是习惯写v // 2 * 2因为一眼就能看懂。如果是追求极致的代码风格可以用位运算版本ans sum(v ~1 for v in count.values()) return ans (1 if any(v % 2 for v in count.values()) else 0)2.4 奇偶判断的两种思路对比判断“是否存在奇数频率字符”常见的有两种做法。做法一是用一个布尔变量标记遍历过程中一旦遇到v % 2 1就置为True。做法二是最后统一判断any(v % 2 1 for v in counts.values())。两种在效率上没有本质差别因为反正都要遍历一遍。需要注意的是有些新手会写成if ans % 2 0: ans 1用累加后的结果来判断。这在部分情况下碰巧是对的但逻辑上是错的。因为累加过程中你可能已经加过了一个奇数对应的偶数部分状态就混乱了。我建议始终用独立的布尔变量逻辑最清晰面试讲起来也不会卡壳。3. 多语言实现与逐步拆解3.1 完整可运行的 Python 解法先给出我最常用的 Python 版本直接在 LeetCode 上能跑通from collections import Counter class Solution: def longestPalindrome(self, s: str) - int: counter Counter(s) length 0 has_center False for count in counter.values(): length count // 2 * 2 if count % 2 1: has_center True return length (1 if has_center else 0)来逐步拆解这段代码。第一步Counter(s)会返回一个字典键是字符值是出现次数。这一步的时间复杂度是 O(n)n 是字符串长度。第二步初始化length 0和has_center False。length用来累计所有能用上的字符数has_center用来标记是否存在可以放在中间的单字符。第三步遍历counter.values()。对每个字符的出现次数countcount // 2 * 2会把它截成不超过它的最大偶数。比如count 33 // 2 11 * 2 2意思就是你最多能把这个出现 3 次的字符用上 2 个。把每个字符的“最大可用偶数”相加就是不考虑中间点时回文串主体部分的长度。第四步如果有任何一个字符的出现次数是奇数说明存在“落单的字符”可以把一个放在正中间总长度加 1。3.2 再给一个 C 版本避免“只看一种语言看不懂”C 写这道题也很短用unordered_map或者数组都行class Solution { public: int longestPalindrome(string s) { int cnt[128] {0}; for (char c : s) { cnt[c]; } int ans 0; bool hasOdd false; for (int i 0; i 128; i) { ans (cnt[i] / 2) * 2; if (cnt[i] % 2 1) { hasOdd true; } } return hasOdd ? ans 1 : ans; } };这里有个细节int cnt[128] {0}必须显式初始化否则数组里是随机值不是 0。用{0}可以把整个数组清零。我第一次刷题时漏过这个结果统计全乱了排错排了半天。3.3 时间复杂度与空间复杂度分析时间复杂度非常明朗遍历字符串统计频率遍历频率表计算结果两次都是线性扫描所以总复杂度是 O(n)。空间复杂度取决于统计结构。如果用了Counter或unordered_map最坏情况是每个字符都不同空间为 O(k)k 是不同字符数。如果用了定长数组空间就是固定的 O(1)因为数组长度不随输入变化。面试时主动把这两个复杂度报出来并且说明“数组方案的空间更优因为字符集固定”是非常加分的。3.4 如何把思路讲给面试官听如果你在面试中被问到这道题我建议按这四步走。第一步复述题目并确认关键点“我需要用 s 中的所有字符重新排列成回文串返回最大可能长度对吗”这一步能防止理解偏差。第二步讲回文结构“回文串的特点是左右对称所以我需要成对的字符。偶数字符全部可以用奇数字符只能用最大的偶数部分。”第三步讲计数方案“因为只要统计出现次数我先遍历一遍字符串做频率统计。这里我用一个哈希表/数组来存每个字符出现的次数。”第四步讲最终判断“累加所有偶数可用次数后如果存在奇数频率的字符说明有字符能单独放在正中间长度再加一。返回结果。”这个过程控制在两分钟左右算法思路、实现细节、复杂度分析全覆盖面试官基本不会再追问什么刁钻问题。4. 常见问题与实战排查实录4.1 最常见的四个坑第一个坑忘记处理“中间点”。只把每个字符的偶数部分相加就直接返回忽略了可能存在的单个字符放在正中间的情况。这个错误很隐蔽因为如果所有字符出现次数都是偶数确实不需要加一但只要有一个字符是奇数频率漏掉加一就会错。建议自测时用s a答案应该是 1用了“所有偶数部分相加”的写法的会得到 0。第二个坑误用“去重字符数”。有的朋友统计完以后想当然地用set(s)的长度去拼回文串或者累加每个字符出现 1 次。这完全跑偏了回文串是需要成对字符的不是每个字符出现一次就能拼成长的。举个例子s aaabbb正确答案是 4比如abba但错误的去重逻辑会得到 2。第三个坑用错了遍历对象。有人在遍历时遍历原始字符串s而不是统计结果每次遇到一个字符就累加它的频率导致一个字符被重复计算多次。正确做法是遍历频率表每个字符只处理一次。第四个坑数组越界或字符集问题。如果用了cnt[c - a]但输入里有大写字母索引就变负数了。要么统一转成小写要么直接开int[128]用 ASCII 码做索引。我比较推荐后者一劳永逸不用管大小写。4.2 一些你可以随手试的测试用例我在刷题时会习惯性地准备几个测试用例覆盖不同边界情况s 空字符串答案应该是 0。s a单个字符答案应该是 1。s ab两个不同字符答案应该是 1。s aa两个相同字符答案应该是 2。s abccccdd题目自带示例答案应该是 7。s aaa奇数频率答案应该是 3因为三个 a 都可以用两个在两侧一个在中间。用这几个用例跑一遍基本能覆盖所有逻辑分支。我经常说一道题的测试用例就是它的“体检报告”覆盖了空输入、单元素输入、全偶数输入、全奇数输入、混合输入逻辑上就稳了。4.3 一次真实的“超时”排查经历我第一次写这道题的解法时用的是一次次插入字符模拟构造回文串的思路。每次选一个频率最高的字符往两边填代码又长又慢结果在一些长字符串用例上超时了。后来才意识到这题根本不需要真的构造回文串——只需要统计长度。我们关心的是“能用多少个字符”而不是“怎么摆放字符”。这其实是一个很重要的思维转变当问题只问“最值”而不是问“方案”的时候很可能不需要真正去构造方案只需要用数学或贪心直接计算。这也是为什么我建议你先看完题目要求想清楚“输出”是什么再决定要不要“模拟过程”。LeetCode 上很多看似要模拟的题目其实都能通过统计一步到位这道题就是最典型的例子。4.4 一道题的举一反三方向409 这道题虽然简单但它可以延伸出几个方向的思考。比如变体一如果题目要求返回最长回文串本身而不是长度你需要在统计完频率后按照“左半 中间点 右半”的顺序拼接字符串。实现方式就是把每个字符的偶数额度一半放在左半一半逆序放在右半奇数频率的字符选一个放中间。变体二如果把题目改成“最多可以删掉多少个字符使剩下的字符串能重排成回文串”本质上就是len(s) - longestPalindrome(s)思路一模一样只是换了个问法。变体三如果输入的字符串很长内存受限可以考虑用位图法记录奇偶状态。因为这道题只关心频率的奇偶性不是具体值所以可以用一个int的每一位代表一个字符是否出现奇数次遍历时异或更新最后统计这个整数里有多少个 1。这种做法空间 O(1)速度还快是位运算爱好者的最爱。4.5 我在实战中的一个小技巧关于统计字符频率有一个极其实用的技巧如果你知道自己只需要处理大小写字母可以直接开一个int[52]的数组索引映射规则自己定义。但更省事的还是int[128]因为 ASCII 码直接可当索引不用做任何换算。在 Python 里则完全不需要考虑这个问题Counter和字典天然适配任意字符。另外当你用int[128]时遍历cnt数组会遍历到很多值为 0 的下标但 128 次循环的开销可以忽略不计不必为了这点性能去维护一个“出现过字符的列表”。代码清晰优先微优化留给真正有性能瓶颈的场景。5. 这道题带给我的启示与一条优化路线讲完了标准解法和坑点我想再聊聊我对这道题的理解。在刷题初期我拿到任何字符串题目都想用双指针去“夹逼”因为很多经典题目都是那么做的。但 409 让我彻底意识到解题的第一步不是套模板而是分析输出要求和数据结构特征。输入是一个无序的字符集合输出是一个长度数值这和“子串”、“子序列”的思路完全不同。如果未来你在面试里碰到变体比如“重排字符串构成最长回文串并输出字典序最小结果”核心逻辑依然不变只需在构造阶段做一次排序或者用优先队列。这条优化路线也从侧面说明了基础计数思路练扎实了复杂的变体不过是在它上面做文章。最后分享一个我现在的代码习惯。所有类似“计算可重排回文串最大长度”的题目我都会先在注释里写清楚“答案 所有偶数频率之和 (存在奇数频率 ? 1 : 0)”然后才开始写代码。这个公式几乎成了我的肌肉记忆它能帮你把逻辑固化成一行共识省去在脑内反复推理的时间。写代码这件事很多时候是先想清楚一句话再落成十行。409 就是这句“话”最简洁的载体。