409. Longest Palindrome

409. Longest Palindrome
Photo by lucas mendes / Unsplash

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

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

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        # for any string to be a palindrome it has to have an even number of letters
        # therefore our longest palindrome is all of the chars in our string which have an even number of letters
        # case sensitive wise
        # we can also use odd numbered letters _if and only if_ they appear in the middle of the string
        
        # Let's create a set of all letters which are odd
        letters = set()
        for c in s:
            if c not in letters:
                letters.add(c)
            else:
                # else it's in letters, it appears twice
                # so it's even
                letters.remove(c)
        # Now our longest palindrome is all of the letters which is
        # s - letters(the set)
        # that means we only get all the even letters
        # we then add + 1 for the single odd letter in the middle
        # if length of letters is 0, it means we only have even letters with no odd letters
        # so our max palindrome is the size of the string itself
        return len(s) - len(letters) + 1 if len(letters) > 0 else len(s)