409. 最长回文串
题目描述
输入一个只含大小写英文字母的字符串 s。用 s 中的字母（每个字母最多用一次，可以不全用）重新排列，组成一个回文串。
大小写视为不同的字符，例如 "Aa" 不是回文串。
返回能组成的最长回文串的长度。
示例 1
输入：s = "abccccdd" 输出：7
解释：可以组成 "dccaccd"，长度为 7。
示例 2
输入：s = "a" 输出：1
解释：单个字母本身就是回文。
数据范围
1 <= s.length <= 2000s只含大写和小写英文字母
解题思路
回文串两侧对称，每种字符成对使用，最多只有中间一个字符可以单独出现。统计每个字符的次数 v，贪心地用掉 v // 2 * 2 个；只要有任何一个字符次数为奇数，就把它的一个放在正中间，答案加 1。
为什么正确
res 始终是已处理字符能提供的成对字符总数，odd 表示是否已有奇数次的字符可以放中间。
复杂度分析
时间 O(n)，空间 O(字符集大小)。
易错点
奇数次的字符不是完全不能用，而是要用掉其中的偶数个；中间只能放一个，所以 odd 只加一次。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def longestPalindrome(self, s: str) -> int:
cnt = {}
for ch in s:
cnt[ch] = cnt.get(ch, 0) + 1
res = 0
odd = 0
for v in cnt.values():
res += v // 2 * 2
if v % 2 == 1:
odd = 1
return res + oddclass Solution {
public int longestPalindrome(String s) {
Map<Character, Integer> cnt = new HashMap<>();
for (char ch : s.toCharArray())
cnt.put(ch, cnt.getOrDefault(ch, 0) + 1);
int res = 0;
int odd = 0;
for (int v : cnt.values()) {
res += v / 2 * 2;
if (v % 2 == 1)
odd = 1;
}
return res + odd;
}
}class Solution {
public:
int longestPalindrome(string s) {
unordered_map<char, int> cnt;
for (char ch : s)
cnt[ch]++;
int res = 0;
int odd = 0;
for (auto& [k, v] : cnt) {
res += v / 2 * 2;
if (v % 2 == 1)
odd = 1;
}
return res + odd;
}
};func longestPalindrome(s string) int {
cnt := map[rune]int{}
for _, ch := range s {
cnt[ch]++
}
res := 0
odd := 0
for _, v := range cnt {
res += v / 2 * 2
if v%2 == 1 {
odd = 1
}
}
return res + odd
}var longestPalindrome = function(s) {
const cnt = new Map();
for (const ch of s)
cnt.set(ch, (cnt.get(ch) || 0) + 1);
let res = 0;
let odd = 0;
for (const v of cnt.values()) {
res += Math.floor(v / 2) * 2;
if (v % 2 === 1)
odd = 1;
}
return res + odd;
};function longestPalindrome(s: string): number {
const cnt = new Map<string, number>();
for (const ch of s)
cnt.set(ch, (cnt.get(ch) || 0) + 1);
let res = 0;
let odd = 0;
for (const v of cnt.values()) {
res += Math.floor(v / 2) * 2;
if (v % 2 === 1)
odd = 1;
}
return res + odd;
}