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