Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example “Aa” is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

1
2
3
4
5
6
7
8
Input:  
"abccccdd"  
Output:
7  
Explanation:  
One longest palindrome that can be built is "dccaccd", whose length is 7.

很简单的一道题目，设一个字符出现次数为n

  1. n 为偶数，那这个字符就一定可以用来组成 Palindrome
  2. n 为奇数，那n - 1个字符就一定可以用来组成 Palindrome, 譬如 n = 1 时，可以用0个字符; n = 3 时，可以用两个字符用来组成 Palindrome.

所以做法就是用HashMap来统计每个字符出现的次数。然后在分奇偶数处理。
最后给的字符串中有至少一个出现次数为奇数的字符，那这个字符可以放在 Palindrome 中间用来组成 Palindrome.

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int longestPalindrome(String s) {
    if (s == null || s.length() == 0)
        return 0;
    int[] map = new int[128];
    for (int i = 0; i < s.length(); i++) {
        map[s.charAt(i)]++;
    }
    int ans = 0;
    for (int n : map) {
        if (n % 2 == 0) {
            ans += n;
        } else {
            ans += n - 1;
        }
    }
    ans += ans == s.length() ? 0 : 1;
    return ans;
}

这里用长度为128的数组来计数，也可以优化为两个26的数组，或是一个58的数组。因为A的ASCII为65，z的ASCII为122. 122 - 65 + 1 = 58