最长回文串

给出一个包含大小写字母的字符串。求出由这些字母构成的最长的回文串的长度是多少。

数据是大小写敏感的，也就是说，"Aa" 并不会被认为是一个回文串。

 注意事项

假设字符串的长度不会超过 1010。

样例

给出 s = "abccccdd" 返回 7

一种可以构建出来的最长回文串方案是 "dccaccd"。

这个题关键的一点就是如何处理奇数个的字符。

如果处理好了奇数个字符，那么这个题就会迎刃而解。原因在于如果是偶数个的字符，一定可以构造回文数。但是奇数个的就不行。所有的奇数个的字符数都要减去1。

最后所有的奇数字符串中只可以保留一个完整的，就是它是多长就在最大回文串中加上多少。但是可想而知，这个奇数的回文串一定是位于整个调整后的回文串的最中间。

否者难以构成回文串。

比如"abbba"是个回文串但是有3个"b",只能放中间才能构成回文串。如果是"abbbccca"有3个"b",3个"c"这时就无法构成回文串，如果想构成回文串那么这两个奇数个的字符

要有一个字符的个数减去1，然后把剩下的那个个数为3的字符放在最中间"acbbbca"或者"abcccba"当然对称的部分顺序也是可以调换的"cabbbac","bacccab"。

最关键的一步就是如何处理奇数个的字符。

通过前面的叙述应该很明白了。就是奇数个的字符。都减去1，再在最后的基础上，判断是否有奇数个的字符。如果有那么结果加上1返回就可以了。

想了很久，调试了很久终于把这个问题给解决了。

public class MaxHuiWenChuan
{
    public int longestPalindrome(String s)
    {
        // Write |your code here
        List<Integer> list = getList(s);
        int i = getMaxHuiWenShu(list);
        System.out.println(i);
        return i;

    }

    /**
     * 解析字符串，获得每个字符的个数，并返回个数list。
     */
    public List<Integer> getList(String s)
    {
        List<Character> list = new ArrayList<>();
        for (char ll = 'a'; ll <= 'z'; ll++)
        {
            list.add(ll);
        }

        for (char ll = 'A'; ll <= 'Z'; ll++)
        {
            list.add(ll);
        }
        List<Integer> list1 = new ArrayList<Integer>();
        for (int i = 0; i < list.size(); i++)
        {
            int k = 0;
            for (int j = 0; j < s.length(); j++)
            {

                if (list.get(i).equals(s.charAt(j)))
                {
                    k++;
                }

            }
            if (k != 0)
            {
                list1.add(k);
            }
        }
        return list1;
    }


    /**
     * 对list集合进行分析。并确定最长的回文数。
     */
    public int getMaxHuiWenShu(List<Integer> list)
    {
        int count = 0;

        if (list.size() == 1)
        {
            count = list.get(0);
            return count;
        }


        boolean hasJiShu = false;
        for (int i = 0; i < list.size(); i++)
        {
            count += (list.get(i) / 2) * 2;
            if (list.get(i) % 2 == 1)
            {
                hasJiShu = true;
            }
        }
        if (hasJiShu)
        {
            count++;
        }
        return count;
    }


    public static void main(String[] args)
    {
        MaxHuiWenChuan m = new MaxHuiWenChuan();
        m.longestPalindrome("abccccdd");
        m.longestPalindrome("aaa");
        m.longestPalindrome("aaabbccc");
        m.longestPalindrome("aaabb");
    }
}

 当然上面的是我自己写的。下面附上一个摘自网上的，代码很精练。值得借鉴。

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) {  
        // Write your code here  
        if(s == null || s.length() == 0){  
            return 0;  
        }  
        boolean hasOod = false;  
        int[] record = new int[52];  
        for(int i = 0;i<record.length;i++){  
            record[i] = 0;  
        }  
        for(int i = 0;i<s.length();i++){  
            char temp = s.charAt(i);  
            if(Character.isUpperCase(temp)){  
                record[temp - 'A' + 0]++;  
            }else{  
                record[temp - 'a' + 26]++;  
            }  
        }  
        int result = 0;  
        for(int i = 0;i<record.length;i++){  
            result += (record[i]/2)*2;  
            if(record[i]%2 == 1){  
                hasOod = true;  
            }  
        }  
        if(hasOod) result++;  
        return result;  
    }  
}