Longest Palindrome

Question (LC.409)

Given a string of letters, return the length of the longest possible palindrome it can form.

Note: The letters are case sensitive.

Example

I: s = "abccccdd"
O: 7 because ccdadcc 

I: s = "a"
O: 1

Analysis

We can count the frequency of each letter in a dictionary. Then build the palindrome like an onion from outside to inside by the most frequent letters. The frequency has be even here to surround the inner string. If a letter is used to surround the inner palindrome and is odd, we can use a flag to track the extra reminder value. For example, ababababa has count 5 and 4. We can use 4 out of 5 as to form the onion layer but the extra a left can also be used in the end as a single middle base.

Code

from collections import defaultdict

class Solution:
    
    def longestPalindrome(self, s: str) -> int:
        
        if len(s) == 0:
            return 0
        
        letter_freq: Dict[str, int] = defaultdict(int)
        
        for cha in s:
            letter_freq[cha] += 1

        sorted_keys = sorted(letter_freq, key=letter_freq.get, reverse=True)
        
        max_len = 0 
        extra_one = False
        
        for i in range(len(sorted_keys)):
            cur_freq = letter_freq[sorted_keys[i]]
            
            if cur_freq == 1:
                max_len += cur_freq
                return max_len
            
            if is_even(cur_freq):
                max_len += cur_freq
            else:
                max_len += cur_freq - 1
                extra_one = True
            
        if extra_one:
            return max_len + 1
        
        return max_len
        
        
def is_even(freq: int) -> bool:
    return freq %  2 == 0

Time Complexity

O(n) time (create dictionary, iterate through sorted keys)

O(n) space (dictionary and sorted keys)