LeetCode 409: Longest Palindrome (Character Frequency Parity)
LeetCode 409Hash TableStringInterviewToday we solve LeetCode 409 - Longest Palindrome.
Source: https://leetcode.com/problems/longest-palindrome/
English
Problem Summary
Given a string s containing uppercase/lowercase letters, return the length of the longest palindrome that can be built using its characters.
Key Insight
For each character count c, we can always use the largest even part: c / 2 * 2. If at least one character has an odd count, we can place exactly one odd character in the center, adding +1.
Brute Force and Limitations
Trying all permutations/combinations is infeasible. The palindrome structure only depends on frequency parity, so counting is sufficient.
Optimal Algorithm Steps
1) Count each character frequency.
2) Accumulate ans += (count / 2) * 2 for every character.
3) If ans < s.length(), there exists an odd count, so return ans + 1; otherwise return ans.
Complexity Analysis
Time: O(n).
Space: O(1) for fixed alphabet (or O(k) for general charset).
Common Pitfalls
- Forgetting the center +1 when odd counts exist.
- Treating uppercase and lowercase as the same character (they are different).
- Adding all odd counts directly instead of only one center character.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int longestPalindrome(String s) {
int[] freq = new int[128];
for (int i = 0; i < s.length(); i++) {
freq[s.charAt(i)]++;
}
int ans = 0;
for (int c : freq) {
ans += (c / 2) * 2;
}
if (ans < s.length()) ans++;
return ans;
}
}func longestPalindrome(s string) int {
freq := make([]int, 128)
for i := 0; i < len(s); i++ {
freq[s[i]]++
}
ans := 0
for _, c := range freq {
ans += (c / 2) * 2
}
if ans < len(s) {
ans++
}
return ans
}class Solution {
public:
int longestPalindrome(string s) {
vector freq(128, 0);
for (char ch : s) {
freq[(int)ch]++;
}
int ans = 0;
for (int c : freq) {
ans += (c / 2) * 2;
}
if (ans < (int)s.size()) ans++;
return ans;
}
}; class Solution:
def longestPalindrome(self, s: str) -> int:
freq = [0] * 128
for ch in s:
freq[ord(ch)] += 1
ans = 0
for c in freq:
ans += (c // 2) * 2
if ans < len(s):
ans += 1
return ansvar longestPalindrome = function(s) {
const freq = new Array(128).fill(0);
for (const ch of s) {
freq[ch.charCodeAt(0)]++;
}
let ans = 0;
for (const c of freq) {
ans += Math.floor(c / 2) * 2;
}
if (ans < s.length) ans++;
return ans;
};中文
题目概述
给定字符串 s（包含大小写字母），你可以重排字符。请返回能够构造出的最长回文串长度。
核心思路
每种字符出现次数为 c 时，回文两侧最多能用掉 (c / 2) * 2 个字符（偶数部分）。如果存在任意奇数次字符，还可以把其中一个字符放在回文中心，多加 1。
暴力解法与不足
枚举所有排列/组合几乎不可行。该题只与“每个字符频次的奇偶性”相关，因此统计频次即可。
最优算法步骤
1）统计每个字符的出现次数。
2）对每个计数累加 (count / 2) * 2。
3）若 ans < s.length()，说明存在奇数计数，可放一个中心字符，返回 ans + 1；否则返回 ans。
复杂度分析
时间复杂度：O(n)。
空间复杂度：固定字符集下为 O(1)（一般字符集记作 O(k)）。
常见陷阱
- 有奇数计数时忘记给中心位加 1。
- 把大小写字符当成同一个字符处理（题目里是区分的）。
- 把所有奇数都加进去（实际上中心只能放 1 个字符）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int longestPalindrome(String s) {
int[] freq = new int[128];
for (int i = 0; i < s.length(); i++) {
freq[s.charAt(i)]++;
}
int ans = 0;
for (int c : freq) {
ans += (c / 2) * 2;
}
if (ans < s.length()) ans++;
return ans;
}
}func longestPalindrome(s string) int {
freq := make([]int, 128)
for i := 0; i < len(s); i++ {
freq[s[i]]++
}
ans := 0
for _, c := range freq {
ans += (c / 2) * 2
}
if ans < len(s) {
ans++
}
return ans
}class Solution {
public:
int longestPalindrome(string s) {
vector freq(128, 0);
for (char ch : s) {
freq[(int)ch]++;
}
int ans = 0;
for (int c : freq) {
ans += (c / 2) * 2;
}
if (ans < (int)s.size()) ans++;
return ans;
}
}; class Solution:
def longestPalindrome(self, s: str) -> int:
freq = [0] * 128
for ch in s:
freq[ord(ch)] += 1
ans = 0
for c in freq:
ans += (c // 2) * 2
if ans < len(s):
ans += 1
return ansvar longestPalindrome = function(s) {
const freq = new Array(128).fill(0);
for (const ch of s) {
freq[ch.charCodeAt(0)]++;
}
let ans = 0;
for (const c of freq) {
ans += Math.floor(c / 2) * 2;
}
if (ans < s.length) ans++;
return ans;
};
Comments