LeetCode 409. 最长回文串

2026-01-16 HGNULB 约 4 分钟

文章信息 12 个分类 3 个标签

分类

LeetCode CodeTop 简单未解决 10-20 字节跳动快手腾讯百度滴滴拼多多商汤

题目描述

✅ 409. 最长回文串

题意分析

输入一个字符串，可以任意打乱、并且可以丢弃其中一部分字符，问用剩下的字符能拼出的最长回文串有多长。注意输出的是长度这个数字，不是回文串本身。

「可以重新排列」这一条把题目从「找回文子串」彻底改变成了「统计字符够不够用」——字符原本的位置完全不重要，重要的只有每种字符各有几个。

回文串的结构决定了答案的形态。设最终回文串长度为 $L$，那么下标 $i$ 处的字符必须等于下标 $L - 1 - i$ 处的字符。把这些位置两两配对，$L$ 为偶数时所有位置恰好配完，$L$ 为奇数时只剩正中间一个位置落单。因此有两条硬约束：每种字符只能成对使用，一对贡献 2 的长度；整个回文串最多只能有一个字符落单，放在正中间。落单的名额是全局的、只有一个，不是每种字符各有一个。

于是每种字符的可用量就确定了：出现 $c$ 次的字符，能凑出 $\lfloor c / 2 \rfloor$ 对，即贡献 $\lfloor c / 2 \rfloor \times 2$ 的长度；若 $c$ 是奇数，还会剩下 1 个用不掉的字符，它有资格去竞争那唯一的中心位置。只要存在至少一个奇数频次的字符，中心就能填上，答案加 1；一个都不存在时，答案就是所有偶数贡献之和，且此时全串长度必为偶数。

剩下的边界：字符串大小写敏感，'A' 和 'a' 是两个不同字符，"Aa" 的答案是 1 而不是 2；长度为 1 时答案是 1；所有字符频次都是偶数时答案等于字符串长度；所有字符都只出现一次时答案是 1。

解法：统计字符的成对贡献

核心思路

回文串两侧的字符必须成对出现，只有中心位置可以放一个落单字符。题目允许重排，所以字符原来的顺序不重要，只需统计频次。

频次为 count 的字符，可以贡献 count / 2 * 2 个字符：偶数全部使用，奇数先舍去一个。若存在任意奇数频次，最后再把其中一个剩余字符放到中心，答案加 1。

正确性可以从上界和构造两方面说明：每种字符至多贡献其偶数部分，中心至多一个；把所有偶数部分对称放在两侧，再选择一个奇数字符居中，恰好能达到这个上界。

解题步骤

用计数数组统计每个字符的出现次数，大小写分别计数。

累加每种字符的最大偶数贡献 count / 2 * 2。

记录是否存在奇数频次。

若存在奇数频次，给全局唯一的中心位置加 1。

例如 abccccdd 的偶数贡献为 4 + 2 = 6，又存在奇数频次 a、b，中心只能任选一个，因此答案是 7。

代码实现

class Solution {
    public int longestPalindrome(String s) {
        int[] count = new int[128];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)]++;
        }

        int length = 0;
        boolean hasOdd = false;
        for (int frequency : count) {
            length += frequency / 2 * 2;
            hasOdd |= frequency % 2 == 1;
        }
        return length + (hasOdd ? 1 : 0);
    }
}

func longestPalindrome(s string) int {
    count := [128]int{}
    for i := 0; i < len(s); i++ {
        count[s[i]]++
    }

    length := 0
    hasOdd := false
    for _, frequency := range count {
        length += frequency / 2 * 2
        if frequency%2 == 1 {
            hasOdd = true
        }
    }
    if hasOdd {
        length++
    }
    return length
}

复杂度分析

时间复杂度：$O(n)$。扫描字符串一次，再遍历固定大小的字符集。

空间复杂度：$O(1)$。计数数组大小固定为 128，不随输入长度增长。

关键点总结

题目允许重排，决定答案的是字符频次，不是原字符串中的位置。

每种字符先取最大偶数部分，所有奇数字符共同竞争唯一的中心位置。

count / 2 * 2 表示成对字符的数量，不是字符对的数量。

大小写敏感，A 与 a 必须放在不同计数桶中。

易错点总结

给每一种奇数字符都加 1，会错误地使用多个中心位置。

所有频次均为偶数时不能再加 1，否则答案会超过原字符串长度。

使用长度 26 的数组会忽略或错误处理大写字符。

不要把本题误解为最长回文子串；本题允许重排，也允许不使用全部字符。

相似题目

题目	难度	考察点
5. 最长回文子串	中等	不可重排的回文子串
1177. 构建回文串检测	中等	前缀奇偶状态的区间查询
1400. 构造 K 个回文字符串	中等	拆成 K 个回文的可行性
面试题 01.04. 回文排列	简单	能否重排成回文的判定