LeetCode笔记：最长回文串
问题
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。
示例 1:
输入: "abccccdd"
输出: 7
解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
解法
思路：
- 先统计出每个字母出现的次数
- 偶数数量的字母可以直接放在回文串的两边，所以直接取用，奇数数量的字母减掉一个变成偶数数量，也可以取用
- 最后特殊处理下，如果有奇数数量的字母，最大的奇数数量的字母可以放在中间位置，也就是最终结果需要+1
代码：
/**
* @param {string} s
* @return {number}
*/
var longestPalindrome = function (s) {
// 用于统计每一个字母出现的次数
const count = {};
for (let i = 0; i < s.length; i++) {
const str = s[i];
// 重复出现的字母，次数+1
if (str in count) {
count[str] += 1;
} else {
// 新出现的字母开始计数
count[str] = 1;
}
}
let odd = false; // 是否包含奇数
let result = 0; // 结果统计
for (let letter in count) {
const num = count[letter];
// 出现次数为奇数的字母，减去一个即为偶数，可放在回文串的两边
if (num % 2 === 1) {
result += num - 1;
odd = true;
} else if (num % 2 === 0) {
// 取偶数次数的字母
result += num;
}
}
// 只要有一个奇数数量的字母，就可以把其中最大奇数数量的字母放在中间位置，所以会多一个
return odd ? result + 1 : result;
};
评论