🐼409. Longest Palindrome

Easy | Grind 75 | November 3rd Thursday, 2022

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.

Constraints:

• 1 <= s.length <= 2000

• s consists of lowercase and/or uppercase English letters only

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
Explanation: The longest palindrome that can be built is "a", whose length is 1.

SOLUTION

We first loop through the string to count the occurrence of each element and store it in a dictionary. We then add all the frequencies. Note, however, that while summing the frequencies, we can add an odd frequency only once without subtracting 1 from it. This is because, in a palindrome, you can at most have only 1 letter in the middle without its corresponding pair.

class Solution:
    def longestPalindrome(self, s: str) -> int:
        # count the element frequency 
        freq = Counter()
        for element in s: 
            freq[element] += 1
        
        # can have one element with odd number of frequency
        used_odd = False
        # maximum length of palindrome 
        length = 0
        
        for key in freq: 
            # use all the elements if even frequency
            if freq[key]%2 == 0: 
                length += freq[key]
                
            else:
                # an odd frequency element has already been included
                if used_odd:
                    length += freq[key]-1
                # use the whole frequency if this is the first odd freqeuncy being counted
                else:  
                    length += freq[key]
                    used_odd = True
        
        return length
                

TIME AND SPACE COMPLEXITY

Time: O(n) where n is the length of the string. We iterate over all the elements in the string once. And then, in the worst case, we will iterate over all the elements once again while iterating over the dictionary.

Space: O(n) where n is the length of the string. In the worst case where a string contain elements with only single occurence, our dictionary will have to be of size n to store all the frequency.