LeetCode 409. 最长回文串
题目描述
题意分析
从给定字符中选择若干个并任意重排，求能组成的最长回文串长度。原来的相邻关系不影响答案，只需统计字符频次。题目仅包含大小写英文字母，并且区分大小写。
解法：统计字符的成对贡献
核心思路
[!blue]
回文串中，除可能存在的一个中心位置外，其余位置都与另一侧的位置成对，并且一对位置必须放相同字符。某字符出现
frequency次，就最多提供frequency / 2对，即frequency / 2 * 2个字符；奇数频次会剩下一个不能配对的字符。将每种字符的成对贡献相加，得到
length。不同字符的剩余单个字符不能配成一对，而中心最多只有一个位置，因此只要存在奇数频次，就能在length上再加 1，不能为每一种奇数字符分别加 1。这个上限一定可以达到：把每种字符的一半成对字符放在左半边，右半边按相反顺序放置相同字符；若有剩余字符，再任选一个放在中心。这样所有可用字符对都被用上，结果仍是回文，所以不需要枚举排列。若所有频次均为偶数，已经能使用全部字符，不能再增加中心字符。
解题步骤
- 用长度为 128 的数组按字符编码计数。英文字母都在此范围内，大小写自然落入不同的计数位置。
- 遍历频次，将
frequency / 2 * 2累加到length。- 用
hasOdd记录是否出现过奇数频次；一旦为真，就不因后续频次为偶数而清除。- 返回
length + (hasOdd ? 1 : 0)。输入只有一个字符时，成对贡献为 0，中心贡献为 1，无需特殊处理。
代码实现
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)$，其中 $n$ 为字符串长度。扫描字符串一次，再遍历固定的 128 个计数位置。
- 空间复杂度：$O(1)$。计数数组大小固定为 128，不随输入长度增长。
关键点总结
[!green]
- 题目允许重排，决定答案的是字符频次，不是原字符串中的位置。
- 每种字符先取最大偶数部分，所有奇数字符共同竞争唯一的中心位置。
count / 2 * 2表示成对字符的数量，不是字符对的数量。- 大小写敏感，
A与a必须放在不同计数桶中。
易错点总结
[!yellow]
- 给每一种奇数字符都加 1，会错误地使用多个中心位置。
- 所有频次均为偶数时不能再加 1，否则答案会超过原字符串长度。
- 使用长度 26 的数组会忽略或错误处理大写字符。
- 不要把本题误解为最长回文子串；本题允许重排，也允许不使用全部字符。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 面试题 01.04. 回文排列 | 简单 | 原题要求使用全部字符，本题允许舍弃多余奇数频次，保留成对字符并选一个中心。 |
| 267. 回文排列 II | 中等 | 原题生成回文排列，本题只求最大可构造长度，无需枚举排列。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！