The optimal solution to this problem runs in O(n) time and takes O(n) space.
I think this runs in O(n) time and O(logn) space:
from collections import Counter
def longest_palindrome(s):
counter = Counter(s)
final_one = False
result = 0
for c, freq in counter.items():
if not freq % 2:
result += freq
else:
result += freq - 1
final_one = True
return result + final_one
The keyspace for the counter is fixed at 52 possible keys (26 uppercase and 26 lowercase), so we only need log(count) bit space to store the counts.
Course: Grokking Coding Interview Patterns in Python - AI-Powered Learning for Developers
Lesson: Longest Palindrome - Grokking Coding Interview Patterns in Python