刷题刷到中期很多人会回过头去复刷简单题原因很简单Easy 题里的通用思路往往比 Hard 题的奇技淫巧更值钱。LeetCode 409 这题中文一般叫“最长回文串”就是一个典型。题目给一个字符串允许你重新排列它的字符问能构造出的最长回文串长度是多少。别看它标着 Easy里面藏了频率统计、奇偶分析和贪心选择三件事。如果你是刚准备面试的初学者这题是极好的热身如果你已经刷了不少题把这题的思路压缩成一句话“偶数全拿奇数减一最多一个中心”也够你回味一阵。1. 这道题到底在问什么先别急着写代码1.1 原题描述与示例拆解LeetCode 409 的原题描述很简洁给定一个包含大写字母和小写字母的字符串s返回通过重新排列这些字母注意是重新排列不是删除后再排可以构建的最长回文串的长度。换句话说你可以把字符串里的字符随意打乱位置目标是拼出一个回文串回文串越长越好。这里有个容易被忽略的关键点不要求输出具体回文串只要求输出最大长度。所以正常解法不会真的去构造回文串而是通过统计每个字符出现的次数来推算答案。题目给了两个示例输入s abccccdd输出7。一种可行的回文串是dccaccd长度为 7。输入s a输出1。只有一个字符它本身就是回文串。第二个示例很有迷惑性很多人看完会觉得这题太简单直接返回字符串长度不就行了当然不行。反例很现成s abc字符串长度为 3但你最多只能构造出a、b、c这种长度为 1 的回文串因为abc无论怎么排列都不可能左右对称。所以问题的关键不是“字符串有多长”而是“字符出现的次数能不能支撑起回文结构”。1.2 为什么“最长回文串”是入门必刷题这道题在面试里出现频率不低尤其是偏向基础算法的岗位。它好就好在考察点非常集中你需要知道回文串的对称结构你需要动手统计字符频率你需要用贪心思路决定每个字符取多少。很多初学者一看到“哈希表”“贪心”这两个词就紧张但这道题把两者都包装得很轻量。统计频率用哈希表或定长数组都行贪心策略也只有一条规则。做完这题你会很自然地把“回文串问题第一反应先做频率统计”这个习惯带进后续的题里。更重要的是这道题能帮你区分“模拟题”和“推导题”。直接构造回文串是模拟很容易写出一堆边界条件而从频率推长度是推导逻辑简单代码量也小。LeetCode 409 的经典解法只有十几行却能让你体会到算法题里“用数学规律代替暴力模拟”的好处。2. 核心思路回文的结构决定了贪心策略2.1 回文串的对称性本质是“成双成对”回文串的定义是正着读和反着读都一样。用更直白的话说它是一个左右镜像的结构最左边和最右边是同一个字符次左边和次右边是同一个字符依次向中间靠拢。把这个结构翻译成频率语言就是一句话除了最中间可以出现一个单独的字符之外其余每个字符都必须成对出现。举个具体的例子abcba里a和b都出现了两次分别站在两侧c出现了一次站在正中间。再看aabbb是不是回文不是因为b有 3 个成对用掉 2 个后多出 1 个这个多出来的字符没法同时放在左右两侧。当然如果你重新排列成abbba它就可以是回文了这正是题目允许重排的意义。所以判断一个字符串能不能重排成回文只看两件事出现奇数次的字符是不是只有一个。如果超过一个就不可能。而 409 题更进一步它不问“能不能”而是问“最长能有多长”。这就把判断问题变成了最大化问题既然只能有一个落单的字符放在中间那我们就尽量把所有能成对的字符都用上。2.2 频率推长度的计算公式与推导过程假设我们已经统计出每个字符的出现次数第i个字符出现cnt[i]次。根据回文结构我们可以这样做如果cnt[i]是偶数比如 4那这 4 个字符可以全部用上左右各放 2 个。如果cnt[i]是奇数比如 5那最多只能放 4 个左右各 2 个剩下的 1 个暂时“候补”。所有字符都取完偶数部分后再检查有没有候补的单个字符。如果有就挑其中一个放在回文串的最中间让总长度再加 1。所以最终长度可以写成最长长度 所有 cnt[i] 的偶数部分之和 (是否存在奇数 cnt[i] ? 1 : 0)用代码表达等价公式时最常见的写法是ans sum(cnt[i] // 2 * 2 for i) 如果有任意 cnt[i] 是奇数 ans ans 1这里cnt[i] // 2 * 2的作用是向下取到最近的偶数。例如5 // 2 * 2 43 // 2 * 2 21 // 2 * 2 0。它比if cnt % 2 0的分支写法更简洁也不容易漏掉“奇数减一”这个动作。拿题目示例验证一下。abccccdd中a出现 1 次b出现 1 次c出现 4 次d出现 2 次。偶数部分之和是0 0 4 2 6存在奇数频率字符所以再加 1得到7。刚好和示例一致。再验证一个容易错的例子aaabbb。a出现 3 次b出现 3 次。偶数部分之和是2 2 4存在奇数频率所以最终答案是5。你可以手动拼一个abbba长度确实是 5。注意这里千万不能把两个奇数各自剩下的 1 个都加进去因为回文串中间只允许放一个字符。2.3 处理奇数频率的两种实现口径理解了公式之后写代码还有一次选择的机会怎么判断“是否存在奇数频率”。第一种口径是显式标记。遍历频率时用一个布尔变量记录有没有遇到过奇数hasOdd false ans 0 for cnt in counts: ans cnt // 2 * 2 if cnt % 2 1: hasOdd true return ans 1 if hasOdd else ans这种写法的好处是逻辑直白每一行都在表达公式里的一步适合作为面试时的口头讲解版本。第二种口径是利用总长度做隐式判断。先想清楚如果一个字符出现了奇数次那么无论如何都会有一个字符剩下来没法成对所以最终“未使用字符数”恰好等于奇数频率字符的个数。比如aaabbb总长度是 6偶数部分之和是 4剩下 2 个字符无法使用奇数频率字符的个数是 2刚好对上。于是有另一种写法oddCount 0 for cnt in counts: if cnt % 2 1: oddCount 1 return len(s) - oddCount 1 if oddCount 0 else len(s)这个写法很讨巧但面试时容易把自己绕进去。我个人的建议是平时练习两种都写一遍理解它们的等价性但在正式面试或笔试中优先用第一种显式hasOdd的版本因为一旦紧张隐式版本很容易把oddCount和ans的关系讲混。3. 多语言实现Python、C、Java 的代码细节3.1 Python最直白写法与高效写法Python 写这道题非常舒服因为标准库collections.Counter可以直接完成频率统计。最直白的版本如下from collections import Counter class Solution: def longestPalindrome(self, s: str) - int: counts Counter(s) ans 0 has_odd False for cnt in counts.values(): ans cnt // 2 * 2 if cnt % 2 1: has_odd True return ans 1 if has_odd else ans注意Counter返回的是一个字典counts.values()就是每个字符的出现次数。这一版代码的时间复杂度是O(n)空间复杂度是O(字符集大小)LeetCode 上运行绰绰有余。如果你想让代码更“Pythonic”一点可以写成一行的等价形式def longestPalindrome(self, s: str) - int: odd_count sum(cnt 1 for cnt in Counter(s).values()) return len(s) - odd_count 1 if odd_count else len(s)cnt 1和cnt % 2的作用完全一样都是判断奇数。这个一行版本看起来高级但可读性差一些我通常是作为课后思考抛给学生而不是推荐在正式代码里使用。核心原因很简单三个月后你回看代码直白版本一眼就懂一行版本还得重新推导一遍。3.2 C用数组代替哈希表C 的解法有两个常见切入点用unordered_map或者直接开一个定长数组。由于题目明确说明字符串只包含大小写字母ASCII 码范围不超过 128所以开一个int cnt[128]的数组是最省事也最高效的方案。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 freq : cnt) { ans freq / 2 * 2; if (freq % 2 1) { hasOdd true; } } return hasOdd ? ans 1 : ans; } };这段代码里有两个小细节值得展开。第一cnt[c]中的c是char类型它在数组下标位置会被隐式转换成整数a对应 97A对应 65这没有问题。第二如果你担心某些环境下char有符号导致负数下标可以用static_castunsigned char(c)转型或者干脆用unordered_mapchar, int避免数组下标问题。不过 LeetCode 的测试用例集中在英文字母上cnt[128]完全够用。对于追求极致性能的人还可以把第二个循环改成只遍历s中出现过的字符。但本题的字符集最多 128 个遍历固定数组带来的常数开销可以忽略没必要为了这点性能牺牲代码简洁度。3.3 Java 与 JavaScript 的落地提醒Java 的写法和 C 几乎一一对应。用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 freq : cnt) { ans freq / 2 * 2; if (freq % 2 1) { hasOdd true; } } return hasOdd ? ans 1 : ans; } }Java 的char本身就是整数类型cnt[c]会自动取字符的 ASCII 码作为下标比 C 还省心。唯一要注意的是int[]数组默认值就是 0不需要手动初始化。JavaScript 的常规解法是用Map统计或者用charCodeAt()配合数组var longestPalindrome function(s) { const cnt new Array(128).fill(0); for (const ch of s) { cnt[ch.charCodeAt(0)]; } let ans 0; let hasOdd false; for (const freq of cnt) { ans Math.floor(freq / 2) * 2; if (freq % 2 1) { hasOdd true; } } return hasOdd ? ans 1 : ans; };这里一定要用Math.floor(freq / 2)因为 JavaScript 的/运算结果是浮点数直接freq / 2 * 2在freq 3时会得到3而不是我们想要的2。这是 JS 写法中最常见的翻车点也是很多前端小伙伴第一次提交 409 题时发现答案偏大的原因。4. 边界情况与常见错误排查4.1 必测的边界用例题目本身不难但边界条件很容易在面试或笔试的“隐藏测试用例”里翻车。我建议所有人在提交前至少手动跑一遍下面这张表输入预期输出说明0空串没有字符长度只能是 0a1单个字符天然是回文aa2两个相同字符可以成对ab1两个不同字符只能取一个aaa3三个相同字符两个放两边一个放中间aaaa4偶数个相同字符全部可用abc1三个不同字符结果不是 3aaabbb5两个奇数频率只能为一个字符留中心位置aA1大小写是不同字符不能组成长度为 2 的回文最后一行的aA尤其值得注意。题目里写了“包含大写字母和小写字母”意思就是a和A要被当成两个完全不同的字符。如果你使用s.toLowerCase()之类的操作那就把题目理解错了答案也会从正确的1变成错误的2。4.2 高频错误速查表我见过不少人在 LeetCode 409 上提交出错总结下来基本都是下面这几种情况。错误错误写法示例正确做法把所有奇数的剩余 1 个都加上对每个奇数cnt都执行ans 1只允许一个中心字符必须用hasOdd统一判断误以为ab的答案是 2直接返回s.length先做频率统计再按公式计算大小写未区分先转小写再统计保持原字符串直接统计C 只用 26 个数组位int cnt[26]然后cnt[c - a]题目含大写字母用cnt[128]或哈希表JavaScript 忘记取整ans freq / 2 * 2使用Math.floor(freq / 2) * 2忘记空串输出1循环统计后照常计算空串自然得到 0这些错误的共同根源是没有回到回文串的对称性去推导而是凭直觉猜答案。所以在写代码前先在草稿纸上列一遍频率表真的能省不少调试时间。4.3 一个通用的调试流程如果你用某个写法提交后答案是错的我建议按下面的顺序排查第一步看输出是不是比正确值大。如果偏大八成是奇数频率处理出了问题。检查你是不是把所有奇数字符都加了 1或者用freq / 2 * 2时忘了取整。第二步看输出是不是等于字符串长度。如果是再用abc这类全是奇数频率的用例试试多半会暴露问题。第三步确认字符统计是否区分大小写。你可以直接用aA这个用例验证。第四步如果前几步都没问题就把频率表打印出来手算一遍再和代码输出比较。我实际刷题时有个习惯不止跑示例还会随机拼几个真实感的字符串来验证比如aabbccddeeffg这种连续递增的用例。因为示例通常太少无法覆盖“多个奇数频率并存”的情况。5. 从 409 延伸开去相似问题与进阶方向5.1 和“最长回文子串”有什么不同很多人会把 LeetCode 409 和 LeetCode 5最长回文子串搞混因为名字太像了。但两者的难度和思路完全不同。LeetCode 5 要求在原字符串中找出一个连续的子串这个子串本身就是回文并且长度最长。子串意味着字符顺序不能改变也不能重排所以它考察的是双指针、中心扩展或动态规划。LeetCode 409 则完全允许重排字符本质上只关心字符频率不关心它们在原串里的相对位置。一个常用的记忆方法看到“重新排列”这四个字第一反应就应该跳转到频率统计看到“连续子串”才往动态规划和中心扩展方向想。这两道题放在一起对比特别有价值。它提醒我们刷题的时候不要只看表面名词要看清题目给的是“我可以重排”还是“我必须保持原顺序”。同一个“回文”主题两种限制条件下的解法天差地别。5.2 如果要输出具体回文串怎么办LeetCode 409 只要求长度但面试官很喜欢在追问环节加一句“如果把长度换成构造具体回文串你会怎么做”这个问题不难关键是思路清晰。你可以这样做先统计频率然后取一个辅助数组left。遍历每个字符每取到两个相同字符就放进left里。所有成对字符处理完后如果存在奇数频率字符随便挑一个放到中心。最后构造回文串left 中心 left 的逆序。def build_palindrome(s: str) - str: from collections import Counter cnt Counter(s) left [] center for ch, freq in cnt.items(): left.extend([ch] * (freq // 2)) if freq % 2 1 and not center: center ch return .join(left) center .join(reversed(left))这个扩展版同样遵循 409 的核心思想成对字符放两侧最多留一个中心。写完这个版本你会对 409 的公式有更深的理解以前的ans其实就是在计算len(left) * 2 len(center)。5.3 值得继续刷的几道关联题如果你是在为面试集中刷题做完 409 后可以顺着“回文频率”这条线继续往下走。LeetCode 266判断能否重排成回文。这个题就是 409 的精简版只需要统计奇数频率字符的个数看是否小于等于 1。LeetCode 242有效的字母异位词。它也是用频率统计但比较的是两个字符串是否拥有完全相同的字符集合和次数。LeetCode 5最长回文子串。前面提到过重点体会“可重排”和“连续子串”的差异。LeetCode 647回文子串数目。回到原顺序回文的统计适合巩固中心扩展法。LeetCode 516最长回文子序列。这里可以删除字符但不能重排会用到动态规划。刷到后面你会发现回文类题目表面五花八门实际就分两支一支基于“频率可重排”核心是奇偶统计一支基于“顺序不可变”核心是区间 DP 或双指针。409 正好是前一支的起点把它吃透后面几道题理解起来会顺很多。我个人在实际刷题和带人过程中的体会是409 这题的代码谁都能在三分钟内写完但能一次想清楚“为什么奇数频率只能补一个”的人往往对回文结构的理解更扎实。建议你别急着背题解先拿aaabbb、aA、abccccdd这三个用例把思路完整推导一遍再去写代码。等你形成肌肉记忆以后遇到任何“重排字符构造回文”的变体题都能第一时间想到频率统计这条主线。