Problem description:

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
Input:
"abccccdd"

Output:
7

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

Solution:

First, count all characters in the string. Even occurring characters (v[i]%2 == 0) can always be used to build a palindrome. For every odd occurring character (v[i]%2 == 1), v[i]-1 characters can be used. Result is incremented if there is at least one character with odd occurrence number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def longestPalindrome(self, s: str) -> int:
        count = {}
        for c in s:
            if c not in count:
                count[c] = 1
            else:
                count[c] += 1
        
        res = 0
        haveOdd = 0
        for x in count:
            if count[x]%2 == 1:
                haveOdd = 1
                res += count[x]-1
            else:
                res += count[x]
        
        return res + haveOdd

time complexity: $O(n)$
space complexity: $O(n)$
reference:
related problem: