Simple Python O(N) solution using Counter
To solve this problem we need to identify the underlying structure of palindromes. A palindrome can either be made up of just characters which are present on bo
To solve this problem we need to identify the underlying structure of palindromes. A palindrome can either be made up of just characters which are present on both sides of the middle, or it can be created from these symmetrical characters while having a character which sits directly in the middle. That is, in a palindrome such as ```abccba```, the center of the word is the empty space between the two ```c``` characters. In this case, there is an even number of ```a```, ```b```, and ```c```. However, in the word ```kayak```, there is an odd number of ```y``` since it is directly in the middle. This means that constructing the longest possible palindrome from a set of letters involves identifying all of the letters with even counts and then seeing if we have an exta letter we can stick directly into the middle. To do this, we will use the ```Counter``` datatype, which is a ```dictionary``` that (in our case) has letters as its ```keys``` and their counts as its ```values```.  We can go through every value and check whether or not it is even. If it is, then we know we can add all the elements to our final palindrome. If it is not even, then we know we have an exta letter to stick into the middle of our final word. Additionally, if there are an odd number of elements but there are ```3```, ```5```, ```7```, etc. of them, then we could still use ```2```, ```4```, or ```6``` of them to add to either side of the array. This will always be one less than the total count of that element, since we aren\'t sure if we can use the extra character making it an odd number. This would be useful in an example like ```kayyyak```.\n\n**Solution Using Counter; Time: O(N), Space: O(N)**\n```\ndef longestPalindrome(self, s: str) -> int:\n\todd = 0 #whether or not we have any letters with an odd count\n\tans = 0 #answer\n\tfor count in collections.Counter(s).values():\n\t\tif count%2 == 0: #if we have an even amount of the letter\n\t\t\tans += count #we can use the letter\n\t\telse:\n\t\t\todd = 1 #we have found an od\n\t\t\tans += count-1 #we can use all but the 1 of the letter\n\treturn ans + odd #if there was an odd amt of a letter, we can add that letter to the middle of our palindrome\n```\n\n**Thanks for Reading!**\nIf this post has been helpful, please consider upvoting! Also, if I made any mistakes or there are other optimizations, methods I didn\'t consider, etc. please let me know!
['Python']