LintCode - 最长回文串 （容易）

版权声明：本文为博主原创文章，未经博主允许不得转载。

难度：容易

要求：

给出一个包含大小写字母的字符串。求出由这些字母构成的最长的回文串的长度是多少。
数据是大小写敏感的，也就是说，"Aa" 并不会被认为是一个回文串。

样例
给出 s = "abccccdd" 返回 7
一种可以构建出来的最长回文串方案是 "dccaccd"。

思路：

解题容易，注意边界处理。

public class Solution {
    /*
     * @param s: a string which consists of lowercase or uppercase letters
     * @return: the length of the longest palindromes that can be built
     */
    public int longestPalindrome(String s) {
        if(s == null || s.length() == 0){
            return 0;
        }

        //对每个字母计数
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        char[] chars = s.toCharArray();
        for (char c : chars) {
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }
        
        //分别计算偶数情况和奇数情况
        int even = 0;
        int odd = 0;
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            Integer value = entry.getValue();
            if (value % 2 == 0) {
                even += value;
            } else {
                //奇数中把可用的偶数部分拿出来计算
                int tmp = value / 2;
                even += (tmp * 2);
                odd += value % 2;
            }
        }

        int max = 1;
        if (even > 0) {
            max = even;
            if (odd > 0) {
                max += 1;
            }
        }
        return max;
    }
}