Longest Palindrome

Question

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.

Tags

• Hash

Thought

Use a dictionary to count the frequency of each character and then calculate the result. Please notice that the frequency of the character in the middle can be odd number.

Code

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        ch_dict = dict()
        for ch in s:
            if ch not in ch_dict:
                ch_dict[ch] = 1
            else:
                ch_dict[ch] += 1
        result = 0
        for key in ch_dict.keys():
            if ch_dict[key] % 2 == 0:
                result += ch_dict[key]
                del ch_dict[key]
            else:
                result += ch_dict[key] - 1
                ch_dict[key] = 1
        if len(ch_dict) > 0:
            result += 1
        return result