求star

题目#

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

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

示例 1:

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

示例 2:

输入:s = "a"
输入:1

示例 3:

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

提示:

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

题解:key:#

① 记录每个字符出现的次数#

TIP

回文串的特点:

• 每种字符都出现了偶数次
• 奇数长度的回文串时候，中间那个字符可以出现奇数次

所以只需要统计每个字符的出现次数，然后加上出现次数的最大偶数次

最后判断如果此时的长度小于s.length,说明里面有某些字符出现了奇数次，那么给总数+1 即可

注: x&1是用来判断 x 的奇偶性的

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function (s) {
  let cnt = new Array(58).fill(0);
  let ans = 0;
  for (const ch of s) {
    cnt[ch.charCodeAt() - "A".charCodeAt()]++;
  }
  for (let x of cnt) {
    // 取最大的偶数次
    ans += x - (x & 1);
  }
  // 说明里面某个字符出现了奇数次，那么那个字符可以放在回文串的中间，所以额外再加一
  return ans < s.length ? ans + 1 : ans;
};

② 贪心算法#

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function (s) {
  let map = new Map();
  let ans = 0;
  for (const ch of s) {
    if (map.get(ch)) {
      ans += 2;
      map.set(ch, false);
    } else {
      map.set(ch, true);
    }
  }
  if (ans < s.length) ans++;
  return ans;
};