LeetCode 409 题解：最长回文串的构造原理与常见逻辑误区-java教程-PHP中文网

LeetCode 409 题解：最长回文串的构造原理与常见逻辑误区

本文深入剖析 LeetCode 第 409 题“最长回文串”的核心思路，重点指出初学者常犯的关键错误——误将“最大奇频次字符”直接加入结果，而忽略了回文构造中奇数频次字符应至多保留一个中心位、其余均需减1配对的本质规则。

本文深入剖析 leetcode 第 409 题“最长回文串”的核心思路，重点指出初学者常犯的关键错误——误将“最大奇频次字符”直接加入结果，而忽略了回文构造中奇数频次字符应**至多保留一个中心位、其余均需减1配对**的本质规则。

回文串的核心特征是：除最多一个字符（可作为中心）外，其余所有字符必须成对出现（即频次为偶数）。因此，求最长回文串长度的本质，不是“挑一个最大的奇数频次加进去”，而是：

所有偶数频次字符全部可用；
所有奇数频次字符，每个都取其最大偶数部分（即 frequency - 1）；
最终，若存在至少一个奇数频次字符，则整体可额外 +1（作为唯一中心）。

原代码中这一逻辑被严重误解：

if (frequency % 2 == 0)
    count += frequency;
else {
    if (frequency > odd)  // ❌ 错误：比较大小无意义
        odd = frequency;  // ❌ 错误：直接赋值奇数频次，未减1
}
return count + odd;       // ❌ 错误：可能重复计入多个奇数频次的“全量”

例如输入 "aabbc"：

字符频次：a:2, b:2, c:1 → 正确答案应为 5（如 "abcba"）
原代码计算：count = 2+2 = 4, odd = 1, 返回 4+1 = 5 ✅（侥幸正确）
但输入 "aaabbbccc"（a:3, b:3, c:3）：
原代码：count = 0（无偶数），odd = max(3,3,3) = 3，返回 0+3 = 3 ❌（实际可构造 "abccba" 或 "abcacba" 等，长度为 7）
正确做法：每个奇数频次取 3−1 = 2 → count = 2+2+2 = 6，再 +1（因存在奇频次）→ 7

✅ 修正后的逻辑清晰且普适：

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 len = 0;
    boolean hasOdd = false;

    for (int f : freq.values()) {
        if (f % 2 == 0) {
            len += f;
        } else {
            len += f - 1;     // 取最大偶数部分
            hasOdd = true;    // 标记存在奇频次，预留中心位
        }
    }

    return hasOdd ? len + 1 : len;
}</character>

关键总结：