Longest Palindrome

Intuition

• Rules:
  • Any letter that shows up an even number of times contributes to the palindrome
  • Any letter that shows up an odd number of times is guaranteed to show up at least that odd number - 1 times in the palindrome
• For the rest, we know that each letter may show up once in the middle (anywhere else, it would mess up the palindrome).
• Therefore, we do the even count + the odd count - 1 of each letter + 1 if there is any count remaining that is odd.

Code

class Solution:
    def longestPalindrome(self, s: str) -> int:
        hm = Counter(s)
        res = 0
        is_odd = False
        for count in hm.values():
            if count % 2:
                count -= 1
                is_odd = True
            res += count
        if is_odd:
            return res + 1
        return res

Notes

---

References

https://leetcode.com/problems/longest-palindrome/