409. Longest Palindrome (Easy)

Longest Palindrome is an Easy level problem.

Given a string s consisting of uppercase or lowercase characters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, so A is different from a.

The key realization with this problem is that a palindrome of length greater than 1 will have an EVEN number of each character with the exception of the character right in the middle, which can appear once.

The solution, then, is to count up how many times each letter appears in s, then add the even part of each count, then add 1 if any of the letters had an odd count.

IE: "abccccdd" has the following counts:

"a":1

"b":1

"c":4

"d":2

So the palindrome will have 4 "c"s, 2 "d"s and 1 of either "a" or "b" right in the middle, hence the length is 7.

The problem does not ask us to generate the palindrome, only to calculate the length, which makes it easier.

Runtime: 34 ms. Beats 76.19% of users.

Memory: 16.56 MB. Beats 80.97% of users.

class Solution:

def countLetters(self, s: str) -> dict:

letterCounts = {}

for c in s:

curCount = 0

if c in letterCounts:

curCount = letterCounts[c]

curCount += 1

letterCounts[c] = curCount

return letterCounts

def isEven(self, n: int) -> bool:

return n % 2 == 0

def longestPalindrome(self, s: str) -> int:

letterCounts = self.countLetters(s)

palindromeLength = 0

foundOdd = False

for c in letterCounts:

count = letterCounts[c]

# If the count is even then all of this character

# are in the palindrome

if self.isEven(count):

palindromeLength += count

else:

foundOdd = True

# If the count is odd and greater than 1

# then we add the even part.

if count > 1:

palindromeLength += count - 1

# We have at least one odd element, so we can add

# add one character from one odd element to the middle

# of the palindrome

if foundOdd:

palindromeLength += 1

return palindromeLength