# LeetCode 409. Longest Palindrome

## Description

https://leetcode.com/problems/longest-palindrome/

Given a string `s` which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, `"Aa"` is not considered a palindrome here.

Example 1:

```Input: s = "abccccdd"
Output: 7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.
```

Example 2:

```Input: s = "a"
Output: 1
```

Example 3:

```Input: s = "bb"
Output: 2
```

Constraints:

• `1 <= s.length <= 2000`
• `s` consists of lowercase and/or uppercase English letters only.

## Explanation

The longest palindrome length is the sum of all largest even number less than character’s length. If odd number character found, return the sum + 1. Otherwise if no odd number character found , return the sum.

## Python Solution

``````class Solution:
def longestPalindrome(self, s: str) -> int:

counter = {}
for c in s:
counter[c] = counter.get(c, 0) + 1

longest = 0

values = sorted(counter.values(), reverse=True)

find_odd = False

for value in values:
if value % 2 == 0:
longest += value
else:
longest += (value - 1)
find_odd = True

if find_odd:
return longest + 1

return longest
``````
• Time Complexity: O(N).
• Space Complexity: O(N).