本文深入剖析 leetcode 第 409 题“最长回文串”中常见错误实现的根本原因，重点解释为何仅取最大奇数频次字符（而非统一处理所有奇频次）会导致结果错误，并给出正确、可理解的修正方案。
本文深入剖析 leetcode 第 409 题“最长回文串”中常见错误实现的根本原因，重点解释为何仅取最大奇数频次字符（而非统一处理所有奇频次）会导致结果错误，并给出正确、可理解的修正方案。
在构建最长回文串时，核心策略是：所有偶数频次的字符可全部使用；每个奇数频次的字符最多只能贡献 frequency − 1 个字符（使其变为偶数长度），而整个回文串至多允许一个字符出现在中心位置（即出现奇数次）。
你原始代码的关键误区在于这一段逻辑：
else {
if (frequency > odd)
odd = frequency; // ❌ 错误：试图保留“最大的奇数频次”
}这隐含一个错误假设：只需把频次最高的那个奇数字符完整保留，其余奇数字符全部丢弃。但这是不成立的。例如，输入 "aaabbbcc"：
- 字符频次：a:3, b:3, c:2
- 你的代码会取 odd = max(3,3) = 3，count = 2（仅 c 的偶数部分），最终返回 2 + 3 = 5
- 正确构造应为 "abccba" 或 "bacacb"（长度 6）：
→ a 贡献 2 个（3−1），b 贡献 2 个（3−1），c 贡献 2 个，再任选一个奇数字母（如 a）补在中心 → 实际长度 = (3−1) + (3−1) + 2 + 1 = 7？等等——注意：中心只能放1 个字符，不是 1 个“频次”，而是 1 个位置。
更准确的理解是：
- 所有奇频次字符，我们都先取其最大偶数部分（即 frequency − 1），累加到 count；
- 同时，只要存在至少一个奇频次字符，我们就有资格在最终回文中心插入1 个额外字符（任意一个奇频次字符都可担任中心），因此只需用 odd = 1 标记“中心可用”。
✅ 正确逻辑如下：
public int longestPalindrome(String s) {
if (s == null || s.length() == 0) return 0;
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
freq.put(c, freq.getOrDefault(c, 0) + 1);
}
int count = 0;
boolean hasOdd = false;
for (int f : freq.values()) {
if (f % 2 == 0) {
count += f;
} else {
count += f - 1; // 取最大偶数部分
hasOdd = true; // 标记存在奇频次，可置中心
}
}
return hasOdd ? count + 1 : count;
}? 关键总结：
- 回文串长度 = 所有字符“成对使用”的总数 +（0 或 1）
- “成对使用”指每种字符最多用 f − (f % 2) 个（即向下舍入到偶数）
- 中心位不是“挑一个最大的奇数”，而是“只要有一个奇数，就+1”——因为中心只占 1 个位置，与该字符原本出现几次无关
- 边界处理需严谨：空字符串应返回 0（原代码中 s.length()
该思路简洁、符合直觉，且易于扩展（如统计具体回文构成或支持 Unicode 字符时改用 Map 即可）。理解这一点，不仅能修复本题，更能夯实贪心策略在字符串构造类问题中的应用根基。
