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

Note, that it every palindrome we need to use every letter even number of times, maybe except one letter in the middle. Note also, that this condition is also sufficient: if we have frequencies for each letter which are even and one frequence is odd, we can always create palindrome. For example let us have aaaaaa, c, bbbb, then we create aaabbcbbaaa.

So, all we need to do is to count frequencies of each letter and take as much letters as possible. There are two possible cases:

  1. If we have only zero or one letters with odd frequencies, then we can use all the letters.
  2. If we have k>1 letters with odd frequencies, we need to remove exactly k-1 letter to build palindrome.

Complexity: space complexity is O(k), where k is size of used alphabet. Time complexity is O(n), where n is length of our string: we process it once to get counter, then we find reminders of frequencies modulo 2 in O(k).

class Solution:
    def longestPalindrome(self, s):
        odds = sum([freq % 2 for _,freq in Counter(s).items()])
        return len(s) if odds <=1 else len(s) - odds + 1

Oneliner

The same logic can be written as oneliner return len(s) if (o:=sum([f%2 for _,f in Counter(s).items()])) <=1 else len(s)-o+1

If you like the solution, you can upvote it on leetcode discussion section: Problem 0409