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.

思路

用哈希表简单统计一下字符的个数，也可以用数组进行统计；当然，如果字符仅限大写或者小写，还可以用一个整数通过位运算来统计。

如果某一种字符的个数是偶数，自然可以是组成回文；如果统计出来的个数是奇数，前偶数个字符可以组成回文，剩下一个被排除在外。如果存在被排除在外的字符，在最后返回长度的时候加上1即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        hash = {}
        for i in s:
            # 可以用has_key()函数代替，效率更高
            if (i not in hash):
                hash[i] = 1
            else:
                hash[i] += 1
        values = hash.values()
        result = 0
        has1 = 0
        for j in values:
            if ((j % 2 == 0) and (j > 1)):
                result += j
            if ((j % 2 == 1) and (j > 1)):
                result += (j-1)
                has1 += 1
            if (j == 1):
                has1 += 1
        
        if (has1 > 0):
            return result+1
        else:
            return result