LeetCode 409.最长回文串：我的Java代码为何无法正确运行？

我在练习LeetCode 409.最长回文串问题时，自行编写了Java解决方案，但部分测试用例输出不正确。尝试查找同类错误代码的解析未找到，希望有人帮忙分析代码为何无法正确运行。

我的思路与代码 #

我的思路：使用HashMap统计字符串中各字符的出现频率，遍历频率值时累加所有偶数频率，仅将最大的奇数频率加入结果。

代码如下：

public int longestPalindrome(String s) {
    HashMap<Character,Integer> map = new HashMap<>();
    int count = 0;
    int odd = 0;
    if (s.length() <= 0)
        return 1;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (map.containsKey(c)) {
            map.put(c, map.get(c) + 1);
        }
        else
            map.put(c, 1);
    }
    for (int frequency : map.values()) {
        if (frequency % 2 == 0)
            count += frequency;
        else {
            if (frequency > odd)
                odd = frequency;
        }
    }
    return count + odd;
}

我看到了一份可正确运行的代码，但不想直接复制当作自己的成果，希望理解自身代码的问题并进行修正。正确代码如下：

public int longestPalindrome(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    int[] count = new int[128];
    int oddCount = 0;
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i)]++;
    }
    for (int i = 0; i < 128; i++) {
        if (count[i] % 2 != 0) {
            oddCount++;
        }
    }
    if (oddCount == 0) {
        return s.length();
    }
    return s.length() - oddCount + 1;
}

代码错误原因分析 #

你的代码核心问题是对奇数频率字符的处理逻辑错误：
回文串的构造规则是：

1. 所有偶数频率的字符可以全部计入回文长度；
2. 对于奇数频率的字符，每个都可以取「频率-1」（转为偶数）计入长度，最后最多保留1个完整的奇数频率字符作为回文中心。

而你的代码只选取了最大的那个奇数频率加入结果，完全忽略了其他奇数频率字符中「频率-1」的部分，导致少算了大量可使用的字符。

举个反例：输入字符串"aaabbb"，字符频率为a:3、b:3。你的代码会累加0个偶数频率，取最大奇数3，最终返回3，但正确结果应为5（取2个a+2个b+1个中心字符，总长度5）。

修正方案 #

可以按照两种思路修改：

思路1：调整奇数频率的处理逻辑 #

遍历频率时，对每个奇数频率，先将「频率-1」加入计数，同时标记存在奇数频率（最后加1作为中心）：

public int longestPalindrome(String s) {
    HashMap<Character,Integer> map = new HashMap<>();
    int count = 0;
    boolean hasOdd = false; // 标记是否存在奇数频率的字符
    if (s.length() == 0)
        return 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
    for (int frequency : map.values()) {
        if (frequency % 2 == 0) {
            count += frequency;
        } else {
            count += frequency - 1; // 取偶数部分
            hasOdd = true;
        }
    }
    // 如果有奇数，加1作为中心
    return hasOdd ? count + 1 : count;
}

思路2：参考正确代码的逻辑，统计奇数频率的字符数量 #

用总长度减去奇数频率的字符个数，再根据是否存在奇数加1：

public int longestPalindrome(String s) {
    if (s.length() == 0)
        return 0;
    HashMap<Character,Integer> map = new HashMap<>();
    int oddCount = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
    for (int frequency : map.values()) {
        if (frequency % 2 != 0) {
            oddCount++;
        }
    }
    return oddCount == 0 ? s.length() : s.length() - oddCount + 1;
}

内容的提问来源于stack exchange，提问作者Jonathan Rivera