409.最长回文串

2021-04-27

题目

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

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

注意: 假设字符串的长度不会超过 1010。

示例 1:

输入:
"abccccdd"

输出:
7

解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-palindrome 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

  • 回文串：
    正读和反读都相同的字符序列为回文串。

  • 奇数个字符的回文串：
    除中间字符以外，其他字符镜面对称（即其他字符都出现偶数次）。

  • 偶数个字符的回文串：
    所有字符镜面对称（即所有字符都出现偶数次）。

  • 回文串的本质：
    可能除去一个字符以外)其他的字母都出现偶数次。

  • 最长回文串的构成：
    使所有字母尽可能多的出现偶数次 + 1次（如果此时还有字母没用完）。

JS实现

参考实现1：

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function (s) {
  let result = 0;

  // 为奇数的标识
  let odd_mark = false;


  // 创建长度为58的数组，默认填充0，存放每个字母出现的次数
  // A-Z, 65-90; a-z, 97-122
  // 长度为58（26个英文小写字母+26个英文大写字母+大写Z与小写a中间的6个字符）
  const numbers = new Array(58).fill(0);

  // 统计每个字符出现的次数
  for (let ch of s) {
    numbers[ch.charCodeAt() - 65] += 1;
  }

  for (let number of numbers) {
    // 累加出现次数
    result += number;
    // 如果是奇数，结果减1，并设置奇数标识为true
    if (number % 2) {
      result--;
      odd_mark = true;
    }
  }

  if (odd_mark) {
    result++;
  }

  return result;
};

参考实现2：

var longestPalindrome = function (s) {
  let result = 0;

  let odd_mark = false;

  // 统计每个字符出现的次数
  const hashmap = new Map();
  for (let ch of s) {
    if (!hashmap.has(ch)) {
      hashmap.set(ch, 0);
    }
    const number = hashmap.get(ch) + 1;
    hashmap.set(ch, number);
  }

  // 遍历hashmap
  for (let [key, value] of hashmap) {
    result+=value;
    // 如果是奇数，结果减1，并设置奇数标识为true
    if (value % 2) {
      result--;
      odd_mark = true;
    } 
  }

  if (odd_mark) {
    result++;
  }

  return result;
};