409-LongestPalindrome.md

最长回文串

给定一个包含大写字母和小写字母的字符串  s ，返回   通过这些字母构造成的 最长的回文串  。

在构造过程中，请注意 区分大小写 。比如  "Aa"  不能当做一个回文字符串。

示例 1:

输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
示例 2:

输入:s = "a"
输入:1
示例 3:

输入:s = "bb"
输入: 2

提示:

• 1 <= s.length <= 2000
• s  只能由小写和/或大写英文字母组成

思路：

这道题可以运用贪心算法，先来确定一下回文串的概念，除了最中间的字符可以有奇数个以外，其他的字符都是偶数个，所以问题就转换成，偶数个的字符都用上，奇数的字符的用 n/2*2 个，然后再任意加一个奇数字符，就是最大的回文串了。

1. 函数定义：longestPalindrome 函数接收一个字符串 s 作为参数。
2. 创建哈希表：定义了一个空对象 hash 来作为哈希表，用于存储每个字符及其出现次数。
3. 初始化结果变量：定义变量 res 并初始化为0，用于存储最长回文子序列的长度。
4. 第一次遍历：使用 for 循环遍历字符串 s。在循环中，使用字符作为键更新 hash 中的计数。如果字符已经在 hash 中，则其计数加1；如果不在，则初始化计数为1。
5. 计算结果：使用 Object.keys(hash) 获取 hash 中所有的键（即字符串 s 中的不同字符），并使用 forEach 遍历这些键。

• 对于每个字符，通过 Math.floor(hash[item] / 2) * 2 计算出该字符能形成回文的最长长度（因为是回文，所以两端对称，这里取一半长度乘以2）并加到 res 上。
• 然后检查该字符的计数是否为奇数，并且当前 res 的长度是否为偶数。如果是，说明可以添加一个奇数位置的字符来增加回文长度，将 res 加1。

6. 返回结果：遍历结束后，返回 res，即最长回文子序列的长度。

/**
 * @param {string} s
 * @return {number}
 */
const longestPalindrome = (s) => {
  const hash = {};
  let res = 0;
  for (let i = 0; i < s.length; i++) {
    hash[s[i]] = (hash[s[i]] || 0) + 1;
  }
  // 遍历hash表，计算结果
  for (let item in hash) {
    res += hash[item] - (hash[item] % 2); // 总是减去奇数部分，保证形成回文
  }
  // 如果存在奇数个字符，则可以形成中心点
  return res + Object.keys(hash).some((item) => (hash[item] % 2 === 1 ? 1 : 0));
};