409 Longest Palindrome

1. Description

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

 

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

 

constraints :

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

2. Algorithms

If the length of unique alphabet is even, we can add that alphabet into palindrome string. If the length of unique aphabet is odd, we can extract even alphabet to make palindrome string.

 

To make largest palindrome string, we just add final odd length alphabet using + 1.

 

1. Start
2. Make frequency table with Counter method.
3. Declare two variables named res and odd(flag for turning on if there is odd frequency alphabet in s.) and initialize them to 0.
4. Repeat steps through table "freq".
   1. If value of current key is even, add value to res.
   2. If value of current key is odd, add value - 1 to res. Set odd as 1.
5. Return res + odd. (To make longest palindrome string, we need to add one odd alphabet.)
6. End

3. Codes

class Solution:
    def longestPalindrome(self, s: str) -> int:
        freq = Counter(s)
        res, odd = 0, 0
        
        for char in freq : 
            if freq[char] % 2 == 0 : 
                res += freq[char]
            else : 
                res += freq[char] - 1
                odd = 1
                    
        return res + odd

4. Conclusion