1. 题目描述

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

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

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

  1. 示例 1:
  3. 输入:
  4. "abccccdd"
  6. 输出:
  7. 7
  9. 解释:
  10. 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

2. 解题思路

可以看出来，最长回文串两侧出现的次数需要被2整除，如果有一个单一项，可以将其加到中间。

思路就是：

  • 先将字符串转化为数组，并遍历数组，统计每个元素的个数，储存在map中
  • 遍历map，获取能被2整除的元素个数
  • 如果有单一的元素，就取一个，如果没有就不取

    3. 代码实现

    1. /**
    2. * @param {string} s
    3. * @return {number}
    4. */
    5. var longestPalindrome = function(s) {
    6. let arr = s.split('')
    7. let map = {} // map用来储存元素及其数量
    8. // 获取每个元素的个数
    9. for(let i = 0;i < arr.length; i++){
    10.      map[arr[i]] = map[arr[i]] ? map[arr[i]]+1:1 
    11. }
    12. let res = 0
    13. // 遍历map
    14. for(let item in map){
    15.     // 如果元素的个数大于2，就取其中是2的倍数的部分
    16.     if(map[item] >= 2){
    17.         res += Math.floor(map[item]/2)*2
    18.     }
    19.     // 如果有单一的元素，就取一个，只取一次。如果res%2不是0，说明已经加了一次，就不在加了
    20.     if(map[item]%2 === 1 && res%2 === 0){
    21.         res++
    22.     }
    23. } 
    24. return res
    25. };

    4. 提交结果

    409. 最长回文串 - 图1