409. 最长回文串

1、题目描述

 2、题目分析

回文串是一个正着读和反着读都一样的字符串。

因此可以分析出，能够构造出回文字符串的字符串能够存在以下特性，【除了中间的字母，其余的字母肯定都是偶数个】。根据这个特性，遍历字符串，计算每个字母出现的次数。

备注：记录每个字母出现的次数 用【Hashmap】或者【数组】都行（开128是因为ASCII马映射数字就是0-128不包括128）。

代码如下：

class Solution {
    public int longestPalindrome(String s) {
         int count[] = new int[128];
         for(char c : s.toCharArray()){
             count[c]++;
         }
         int ans = 0;      
         for(int v: count){
            //如果是偶数不变，奇数则进行减一位
            ans += v/2*2;
            //允许中间存在一位奇数情况（有奇数个存在，且ans之前是偶数）
            //这样增加+1后，ans为奇数，后面仍然存在多余偶数位就不予累加了
            if(v%2==1 && ans%2==0){
                ans++;
            }
         }
         return ans;
    }
}

复杂度分析

时间复杂度：O(N)，其中 N为字符串 s 的长度。我们需要遍历每个字符一次。

空间复杂度：O(S)，其中 S 为字符集大小。在 Java 代码中，我们使用了一个长度为 128 的数组，存储每个字符出现的次数，这是因为字符的 ASCII 值的范围为 [0, 128)。而由于题目中保证了给定的字符串 s 只包含大小写字母，因此我们也可以使用哈希映射（HashMap）来存储每个字符出现的次数，例如 Python 和 C++ 的代码。如果使用哈希映射，最多只会存储 52 个（即小写字母与大写字母的数量之和）键值对。

备注：上面代码分析

1、记录每个字母出现的次数 用Hashmap或者数组都行（开128是因为ASCII马映射数字就是0-128不包括128）。

2、然后就是记录 每次出现的次数

3、如果是偶数不变，奇数则进行减一位，简练点的代码就是 v / 2 * 2

【关键，这样写很简洁】4、利用v % 2 == 1抓住奇数次（包含1和其他奇数），并且 ans % 2 == 0，第一次的时候 肯定ans是偶数，之后ans就是自增，第二次是v奇数的时候，ans早就是奇数了，然后就不会成立。