[路飞]_leetcode-409-最长回文串

「这是我参与11月更文挑战的第10天，活动详情查看：2021最后一次更文挑战」

[题目地址][B站地址]

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

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

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

示例 1:

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

首先我们来看一下回文串的性质，以示例1中的回文串为例

dccaccd

回文串就是从左向右遍历该字符串，与从右向左遍历字符串的结果是一样的

也就是说回文串的左右两部分是一样的

如果回文串的长度为奇数，则最中间部分为一个字符，反之中间部分为两个相同的字符

在不考虑中间位置的情况下，左右两部分的字符组成是一致的，也就说明，每个字符出现的次数都是偶次的

所以我们可以对输入字符串进行遍历，并用 map 记录每一种字符及其出现的次数

用变量 total 记录可以组成的最长回文串的长度，total 初始化为 0

接下来遍历 map ，如果当前字符出现次数为奇数次，total 累加当前字符次数减1次（因为当前要保证没中字符在结果字符串中出现偶数次）

如果当前字符出现次数为偶数， total 累加当前字符出现次数

最后判断如果 total 等于输入字符串的长度，则说明输入字符串中每一种字符都出现了偶数次，返回 total 即可

反之，说明输入字符串中至少有一种字符出现奇数次，因为我们要找到最长的回文串长度，又因为我们当前再往结果字符串中间放置任何一个字符都不会违反回文串的性质，所以返回 total+1

至此，本题解题思路完成。代码如下：

var longestPalindrome = function(s) {
    const len = s.length,
    map = new Map();
    // 记录出现的字符及其出现次数
    for(let i = 0;i<len;i++){
        const cur = s[i]
        if(map.has(cur)){
            map.set(cur,map.get(cur)+1)
        }else{
            map.set(cur,1)
        }
    }
    // 累加每一种字符出现偶数的次数
    let total = 0;
    for(let item of map){
        if(item[1]%2) total += item[1]-1
        else total += item[1]
    }
    // 如果累加长度小于输入字符串长度
    // 为了求得最长回文串,可以在中间再放置任意字符
    if(total<len) return total+1
    // 如果total===len 说明输入字符串中每一种字符出现次数均为偶数次
    return total;
};
复制代码

至此我们就完成了 leetcode-409-最长回文串

如有任何问题或建议，欢迎留言讨论！