Problem
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.

Solution

To form a palindrome, we know that each character, other than the center group of characters, must appear an even number of times in the string. So, we know that all characters in s which are found an even number of times can be included. Otherwise, for each character in s that appears an odd number of times, but greater than 1, we can include all but 1 occurence of them. Then, to account for the center, which can have an odd number of characters, we add one of any of the letters which appear an odd number of times.

Since we do not have to return the actual palindrome, we can simply find the length of it, without keeping track of the letters added.

class Solution:
    def longestPalindrome(self, s: str) -> int:
        from collections import Counter
        myDict = Counter(s)
        longest_len = 0 
        odd_nums = []
        for key in myDict.keys():
            if myDict[key] % 2 == 0:
                longest_len += myDict[key]
            if myDict[key] % 2 == 1: 
                odd_nums.append(myDict[key])
                longest_len += myDict[key]-1
        if any(num >= 1 for num in odd_nums):
            longest_len += 1 

Runtime This solution has a time complexity of $O(n)$, as we are iterating through the keys of the dictionary, which is built on the input string. It has a space complexity of $O(n)$.

Back to Greedy Algorithm Problems

---

anusha-murali.github.io