LeetCode 409 题解：为什么你的最长回文串算法逻辑有误？-java教程-PHP中文网

本文深入剖析 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;
}</character>

? 关键总结：