Longest Palindrome

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:

Input:  
"abccccdd"

Output:  
7

Explanation:  
One longest palindrome that can be built is "dccaccd", whose length is 7.  

描述与分析：

给了我们一个字符串，让我们找出可以组成的最长的回文串的长度，由于字符顺序可以打乱，所以问题就转化为了求偶数个字符的个数，我们了解回文串的都知道，回文串主要有两种形式，一个是左右完全对称的，比如noon, 还有一种是以中间字符为中心，左右对称，比如bob，level等，那么我们统计出来所有偶数个字符的出现总和，然后如果有奇数个字符的话，我们取出其最大偶数，然后最后结果加1即可

复杂度分析

时间复杂度: O(N)

空间复杂度: O(1)

Swift：

class Solution {  
    func longestPalindrome(_ s: String) -> Int {
        var count: Array<Int> = Array(repeating: 0, count: 256)

    for c in s.utf8 {
        let char = Int(c)
        count[char] = count[char] + 1
    }

    var total = 0
    var odd = false

    for item in count {
        if item % 2 == 0 {
            total += item
        }
        else {
            total += (item - 1)
            odd = true
        }
    }

    if odd {
        total += 1
    }

    return total
    }
}

C++：

class Solution {  
public:  
    int longestPalindrome(string s) {
        int res = 0;
        bool mid = false;
        unordered_map<char, int> m;
        for (char c : s) m[c]++;
        for (auto it = m.begin(); it != m.end(); ++it) {
            res += it->second;
            if (it->second % 2 == 1) {
                res -= 1;
                mid = true;
            }
        }

        return mid? res + 1 : res;
    }
};

Java:

class Solution {  
    public int longestPalindrome(String s) {
        int[] count = new int[128];
        for (char c: s.toCharArray())
            count[c]++;

        int ans = 0;
        for (int v: count) {
            ans += v / 2 * 2;
            if (ans % 2 == 0 && v % 2 == 1)
                ans++;
        }
        return ans;
    }
}

Python：

class Solution:  
    def longestPalindrome(self, s):
        ans = 0
        for v in collections.Counter(s).itervalues():
            ans += v / 2 * 2
            if ans % 2 == 0 and v % 2 == 1:
                ans += 1
        return ans

本题来自:leetCode