力扣-409-计算一组字符集可以组成的回文字符串的最大长度

题目：
409. Longest Palindrome(easy)

题目大意：
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。

示例 1:

1 2 3 4 5 6

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

解题思路：
回文字符串中除了会出现最中间有一个单独的字符外，其他位置上的字符都出现了偶数次(至少两次)，所以要统计字符串中出现偶数次字符的个数，加上(奇数次-1)次字符的个数
此外，如果前一步统计的长度比原始长度小，则说明某个字符出现了奇数次，所以可以安排一个字符放在正中间，统计长度就要加一。
注意：大写A的ASCii码为65，小写z的ASCii码为122，而且中间大小写字母不连续，所以干脆生成个58长度的整形数组，用来记录字符出现的次数。

代码中：
如果字符出现次数cnt是奇数次，那应该将ans+（cnt-1），如果是偶数次，那就ans+cnt；（cnt&1）就是求出count的二进制表示最后一位，如果cnt是奇数就等于1，如果是偶数就等于0； cnt - (cnt & 1)就是cnt-1（cnt是奇数）或cnt-0（cnt是偶数）

代码：

1
2
3
4
5
6
7
8
9
10
11
12

Java:
public int longestPalindrome(String s){
    int[] cnts = new int[58];
    for(char ch : s.toCharArray()){
        cnts[ch - 'A'] ++;
    }
    int ans = 0;
    for(int cnt : cnts){
        ans += cnt - (cnt&1);
    }
    return ans < s.length() ? ans + 1 : ans;
}