Although come back to normal life, we still admire those who see the daylight in fearless years.
尽管最终又回到平凡的生活，人们还是钟爱那些在无畏岁月里看到曙光的人。
来源：LeetCode第409题
难度：简单
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如"Aa"不能当做一个回文字符串。
注意:
假设字符串的长度不会超过1010。
示例 1:
输入:
"abccccdd"
输出:
7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
回文串有两种组成形式，一种是偶数的比如"abba"，一种是奇数的比如"abcba"。所以回文串中每个字符要么都是偶数个，要么只有一个字符的个数是奇数，其他都是偶数。
因为这题让求的是可以构造的最长回文串，我们只需要把所有字符截取最大的偶数个，统计他们的和，如果还有剩下的字符，最后再加1，如果没有，最后不用再加了。
比如字符串"aaaaabbbcc"长度是10，a的最大偶数是4，b的最大偶数是2，c的最大偶数也是2，他们的和是4+2+2=8，小于字符串长度10，所以最后要加1，也就是字符串"aaaaabbbcc"可以构造的最长回文串长度是9。
比如字符串"aaaabbcc"长度是8，a的最大偶数是4，b的最大偶数是2，c的最大偶数也是2，他们的和是4+2+2=8，等于字符串长度8，所以最后不需要再加1，也就是字符串"aaaabbcc"可以构造的最长回文串长度是8。
搞懂了上面的分析，代码就简单多了，来看下
1public int longestPalindrome(String s) {
2 int[] map = new int[256];
3 //统计每个字符的个数
4 for (char ch : s.toCharArray())
5 map[ch]++;
6 int res = 0;
7 int mask = -2;
8 for (int count : map) {
9 //每个字符的个数取最大偶数，然后相加
10 res += count & mask;
11 }
12 //如果相加的和小于字符串的长度，最后还要加1
13 return res < s.length() ? res + 1 : res;
14}
上面可能不容易理解的是这样一行代码
因为mask是-2，count&-2的意思就是如果count是偶数，计算的结果还是count，如果count是奇数，计算的结果是count-1。直接看可能不直观，把-2转化为二进制就明白了。
11111111 11111111 11111111 11111110
除了上面的统计方式以外，我们还可以使用集合Set来统计，代码如下
1public int longestPalindrome(String s) {
2 int res = 0;
3 Set<Character> set = new HashSet<>();
4 for (char ch : s.toCharArray()) {
5 //如果set中有字符ch，remove方法会
6 //返回true，否则返回false
7 if (set.remove(ch)) {
8 //当前字符ch，出现了2次
9 res += 2;
10 } else {
11 //当前字符ch，只出现1次
12 set.add(ch);
13 }
14 }
15 return res + (set.isEmpty() ? 0 : 1);
16}
或者还可以这样写，但不管怎么写，原理还是不变的，换汤不换药。
1public int longestPalindrome(String s) {
2 boolean[] map = new boolean[256];
3 int res = 0;
4 for (int i = 0; i < s.length(); i++) {
5 res += map[s.charAt(i)] ? 2 : 0;
6 map[s.charAt(i)] = !map[s.charAt(i)];
7 }
8 return res < s.length() ? res + 1 : res;
9}
