LeetCode 409 最长回文串哈希表计数与回文构造条件的完整解析LeetCode-Book 题解【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读本题来自《Krahets 笔面试精选 88 题》对应 LeetCode 409「Longest Palindrome」是哈希表 / 字符计数类题目的典型代表给定一个包含大小写字母的字符串s返回用这些字符可以构造出的最长回文串的长度。本篇基于 selected_coding_interview/docs/409. 最长回文串.md 展开完整继承原文档的解题思路、三语言代码与复杂度分析并结合本仓库 selected_coding_interview/codes 下的源码实现与测试驱动补充回文串充要条件的数学推导、边界用例与扩展思路。读完你将掌握「字符计数 → 向下取偶 → 补中心」这一通用构造方法并能在 Python / Java / C 中直接落地。一、题目核心回文串的对称性决定了答案的边界「回文串」是指倒序后与自身完全相同的字符串即具有关于中心轴对称的性质。以字符串abccba、racecar为例观察其字符分布可以发现两条基本规律当回文串长度为偶数时以中心轴为界左右镜像因此所有字符都必须出现偶数次例如abccba中a、b、c各出现 2 次当回文串长度为奇数时中心位置可以放置一个单独的字符该字符出现奇数次其余所有字符出现偶数次例如racecar中e只出现 1 次r、c、a各出现 2 次。由此可以得到字符串能被构造成回文串的充要条件除了一种字符出现奇数次外其余所有字符出现偶数次。注意两点细节「一种字符出现奇数次」是上限而非必须——如果所有字符都出现偶数次同样可以构造出长度为偶数的回文串出现奇数次的字符其多出的那 1 个count % 2 1只能被放在回文串的正中心且整条回文串至多只有一个中心字符。这两条结论是本题算法的全部理论依据原文档在「解题思路」一节已明确给出下面将它与算法步骤一一对应。二、算法设计HashMap 计数 向下取偶 中心补位基于上述充要条件本题并不需要真正构造出回文串只需求出能参与构造成回文串的最大字符数。判别流程如下与 409. 最长回文串.md 的步骤完全对应统计字符频次借助一个 HashMap键为字符、值为出现次数遍历字符串s完成计数这一步的时间与字符串长度成正比遍历频次表累计回文长度将当前字符的出现次数向下取偶数即若为偶数则不变若为奇数则减 1因为出现偶数次的字符可以全部对称排布计入res若当前字符出现次数为奇数说明存在「多出的 1 个字符」可将该字符放到回文串中心因此将标志位odd置 1返回res oddres是所有偶数部分的累加odd表示是否允许在中心补上 1 个字符有任一奇数频次字符时取 1否则为 0。关键一行res count - count % 2count - count % 2正是「向下取偶」的实现count 4偶数res 44 个字符全部可用count 3奇数res 2取其中 2 个对称排布剩余 1 个留作中心候选。同时注意odd用「或 1」而非「累加」的语义无论有多少种字符出现奇数次回文串中心最多只能放 1 个字符因此odd只需记录「是否存在」即可。这也是原文档在 Python、Java、C 三种实现中统一采用if (rem 1) odd 1;而非odd rem的原因。边界用例验证输入s频次分析resodd输出abccccddLeetCode 示例a:1, b:1, c:4, d:242617如dccaccdexample仓库测试用例e:2, x/a/m/p/l:1213aaaaa:4404aa:1011空串无000其中example正是本仓库 Python 与 Java 测试驱动使用的输入下面第三、四节会实际运行验证。三、三语言实现完整可运行的源码原文档提供了 Python、Java、C 三种语言的核心解法代码以下代码与仓库中的实现保持一致。本仓库将其整理为带测试驱动的可运行工程目录结构如下Pythonselected_coding_interview/codes/python/lc_409_longest_palindrome.pyJavaselected_coding_interview/codes/java/lc_409_longest_palindrome/lc_409_longest_palindrome.java公共工具包selected_coding_interview/codes/python/include提供collections、defaultdict等依赖见init.py与 selected_coding_interview/codes/java/includePythonfrom include import * # 提供 collections、defaultdict 等仓库测试驱动约定 class Solution: def longestPalindrome(self, s: str) - int: # 统计各字符数量 counter collections.defaultdict(int) for c in s: counter[c] 1 res, odd 0, 0 # 统计构造回文串的最大长度 for count in counter.values(): # 将当前字符出现次数向下取偶数并计入 res rem count % 2 res count - rem # 若当前字符出现次数为奇数则将 odd 置 1 if rem 1: odd 1 return res oddJavaimport include.*; // 仓库 Java 工程统一引入工具包 import java.util.*; class Solution { public int longestPalindrome(String s) { // 统计各字符数量 HashMapCharacter, Integer counter new HashMap(); for (int i 0; i s.length(); i) counter.merge(s.charAt(i), 1, (a, b) - a b); // 统计构造回文串的最大长度 int res 0, odd 0; for (Map.EntryCharacter, Integer kv : counter.entrySet()) { // 将当前字符出现次数向下取偶数并计入 res int count kv.getValue(); int rem count % 2; res count - rem; // 若当前字符出现次数为奇数则将 odd 置 1 if (rem 1) odd 1; } return res odd; } }Java 细节counter.merge(s.charAt(i), 1, (a, b) - a b)等价于「若键不存在则放入 1否则把旧值与 1 相加」是 Java 8 对「计数累加」的惯用简写可替代「先getOrDefault再put」的冗长写法。Cclass Solution { public: int longestPalindrome(string s) { // 统计各字符数量 unordered_mapchar, int counter; for (char c : s) counter[c]; // 统计构造回文串的最大长度 int res 0, odd 0; for (auto kv : counter) { // 将当前字符出现次数向下取偶数并计入 res int count kv.second; int rem count % 2; res count - rem; // 若当前字符出现次数为奇数则将 odd 置 1 if (rem 1) odd 1; } return res odd; } };三种实现的核心逻辑完全同构count % 2判断奇偶 →res count - rem向下取偶 →odd记录中心字符是否存在仅语言语法不同。四、仓库运行验证测试驱动与实测结果本仓库为每道题都配备了可独立运行的测试驱动Driver Code。Python 侧测试驱动位于 lc_409_longest_palindrome.py 文件末尾Java 侧位于同名.java文件的main方法中# Test Case test_input example # Driver Code slt Solution() result slt.longestPalindrome(test_input) print(result)在仓库根目录执行 Python 版本实测输出为3与第二节边界用例表中的推演一致example中e出现 2 次计入res 2其余 5 个字符各出现 1 次存在奇数频次odd 1最长可构造回文串长度为2 1 3例如epe、exe等。由此验证了题解的正确性算法只统计「能构成回文串的最大长度」并不关心具体构造出哪个回文串这使问题从构造问题转化为纯计数问题。五、复杂度分析时间复杂度 $O(N)$其中 $N$ 为字符串s的长度。遍历字符串s统计频次需要线性时间随后遍历哈希表counter由于字符集大小有上界见下同样视为线性时间。空间复杂度 $O(1)$本题输入为字母组成的字符串ASCII 字符数量为 128哈希表counter的键最多不超过 128 个即最多使用 $O(128) O(1)$ 空间。需要说明适用前提$O(1)$ 的空间结论依赖于字符集有固定上界如 ASCII 128 个字符。若题目改为 Unicode 全量字符集例如将任意中文字符也视为输入范围哈希表理论上可增长到与 $N$ 同阶此时空间复杂度应表述为 $O(K)$$K$ 为实际出现的不同字符数$K \le N$。本题输入仅含字母因此 $O(1)$ 严格成立。六、延伸思考更精简的变体实现变体一用哈希集合记录奇偶性题目不关心具体频次、只关心「奇偶」因此可以只用一个哈希集合替代频次表遍历每个字符若集合中已存在则删除表示配对成功一次否则插入最终集合中剩余的元素数量odd就是「出现奇数次的字符种数」答案即为class Solution: def longestPalindrome(self, s: str) - int: odd_set set() for c in s: if c in odd_set: odd_set.remove(c) # 又出现一次抵消奇偶 else: odd_set.add(c) # 首次出现标记为奇数次 return len(s) - len(odd_set) (1 if odd_set else 0)原理len(s) - len(odd_set)恰好等于所有频次的偶数部分之和与「向下取偶后累加」等价odd_set非空时在中心补 1。该变体时间仍为 $O(N)$空间仍受字符集上界约束为 $O(1)$且省去了频次统计与二次遍历。变体二固定数组代替哈希表面向字母输入由于本题输入仅含大小写字母52 种也可用长度为 128 的数组代替哈希表在部分语言中常数更小。需要强调这是对「字符集有上界」这一前提的利用不能推广到无界字符集。同类问题的关联本仓库中其他哈希表 / 计数类题目可作为配套练习136. 只出现一次的数字位运算 XOR 替代计数387. 字符串中的第一个唯一字符计数 二次遍历242. 有效的字母异位词两串频次对比。这些题目与 409 共享「哈希计数」的核心范式适合集中刷题巩固。七、小结本题的关键结论可以浓缩为一句口诀偶数全用奇数取偶至多一个中心字符。回文串构造的充要条件是「最多一种字符出现奇数次」算法三步骤哈希表统计频次 →count - count % 2向下取偶累加 → 检测到奇数频次则将中心标志置 1时间复杂度 $O(N)$、空间复杂度 $O(1)$输入为 ASCII 字符集前提下本仓库提供了 Python 与 Java 可运行工程实测example输出 3与推演一致可直接作为刷题与复习的参考实现。掌握本题后遇到「能否构成回文 / 最长回文长度 / 回文重排」等变式题都可以迅速迁移这套计数思维。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考