# Longest Palindrome

Hash Table

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

### # HashMap

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

``````def longestPalindrome(self, s: str) -> int:
hashmap = {}
res = 0
for c in s:
hashmap[c] = hashmap.get(c, 0) + 1
for c in hashmap:
res += (hashmap[c] // 2) * 2
if hashmap[c] % 2 == 1 and res % 2 == 0:
res += 1
return res
``````
1
2
3
4
5
6
7
8
9
10

Or simply use `Counter`:

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

### # HashSet

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

``````def longestPalindrome(self, s: str) -> int:
hashset = set()
for c in s:
if c in hashset:
hashset.remove(c)
else:
remove = len(hashset)
if remove > 0:
remove -= 1
return len(s) - remove
``````
1
2
3
4
5
6
7
8
9
10
11