# Longest Palindrome

## # Solution

The answer is the count of characters that has even number of appereances. For characters that has odd number of appereances, their appereances minus 1 will make their apperances even. And finally we can put an unused character in the middle of the palindrome.

All the following three solutions have linear time and space.

### # Vanilla Hash Table

Store the counts of chars in hash table `hm`. For each char in `hm`, only plus an even count, then plus 1 if the char `hm[i]` is odd and `res` is even.

``````def longestPalindrome(self, s: str) -> int:
hm = {}
res = 0
for c in s:
hm[c] = hm.get(c, 0) + 1
for i in hm:
res += (hm[i]//2)*2
if hm[i]%2==1 and res%2==0:
res += 1
return res
``````

Or could use the `collections.Counter(s).values()` method w/ only 1 for loop.

``````def longestPalindrome(self, s: str) -> int:
res = 0
for v in collections.Counter(s).values():
res += v // 2 * 2
if res % 2 == 0 and v % 2 == 1:
res += 1
return res
``````

### # Improved Hash Table

Only store chars w/ odd counts in a HashSet `hs`. Calculate result by `len(s) - len(hs)`, and further subtract `1` if `len(hs)>0` (chars w/ odd counts).

``````def longestPalindrome(self, s: str) -> int:
hs = set()
for c in s:
if c in hs:
hs.remove(c)
else: