[Python3] Hash map approach with line by line comments!
In order to construct a palindrome, there are two cases we need to consider:\n(1) the result palindrome contains an odd number of word from words - this means t
In order to construct a palindrome, there are two cases we need to consider:\n(1) the result palindrome contains an odd number of ```word``` from ```words``` - this means the word in the middle of the palindrome contains 2 same letters. e.g., ```clclaalclc```\n(2) the result palindrome contains even number of ```word``` from ```words``` - this means both the selected ```word``` and its reverse ```word[::-1]``` exist.\n\nWe also need to consider that the given ```words``` may contain duplicates, so using a counter (hash map) that counts the frequency of each ```word``` in ```words``` seems like a good idea.\n\n**Algorithm:**\n(1) Creates a hash map to count the frequency of each ```word``` in ```words```.\n(2) Use ```mid``` to represent if result is in case1 (mid=1) or case2 (mid=0), initially mid=0.\n(3) Go over the counter:\n>if the word contains two same letters and its frequency is odd, one of these words can be placed in the middle, and we are in case 1, ```mid``` become 1. \nWe increase the result by frequency if it is even. If the frequency is odd, we add frequency-1 to the result.\n\n>elif the word and its reverse both exist, and word[0]!=word[1], we add the minimum frequency of the word and its reverse to the result.\n\n(4) We will return 2 times the (result + mid) since we only counted the frequency of the selected word (mid==1 if it is case 1 and 0 for case 2).\n\n**Time Complexity: O(n)**\n```\nclass Solution:\n    def longestPalindrome(self, words: List[str]) -> int:\n    \t\n    \t### count the frequency of each word in words\n        counter = Counter(words)\n        \n        ### initialize res and mid. \n        ### mid represent if result is in case1 (mid=1) or case2 (mid=0)\n        res = mid = 0 \n\n        for word in counter.keys():\n            \n            if word[0]==word[1]:\n            \t### increase the result by the word frequency\n                res += counter[word] if counter[word]%2==0 else counter[word]-1\n                ### set mid to 1 if frequency is odd (using bit-wise OR to make it short)\n\t\t\t\t### using bit-wise OR to make sure that once mid is 1 it cannot go back to 0 (learned from lee215)\n                mid |= counter[word]%2\n            \n            elif word[::-1] in counter:\n            \t### increase the result by the minimum frequency of the word and its reverse\n            \t### we do not do *2 because we will see its reverse later\n                res += min(counter[word],counter[word[::-1]])\n        \n        ### since we only count the frequency of the selected word\n        ### times 2 to get the length of the palindrome\n        return (res + mid) * 2\n```\n\n**Upvote** if you like this post.\n\n**Connect with me on [LinkedIn](https://www.linkedin.com/in/meida-chen-938a265b/)** if you\'d like to discuss other related topics\n\n\uD83C\uDF1F If you are interested in **Machine Learning** || **Deep Learning** || **Computer Vision** || **Computer Graphics** related projects and topics, check out my **[YouTube Channel](https://www.youtube.com/@meidachen8489)**! Subscribe for regular updates and be part of our growing community.
[]