⚡️Easy Python 3 | Greedy Solution ⚡️O(n) | beats 85% | 64ms 🔥
Intuition\n\nPalindrome is - a word that reads the same when read from left to right and from right to left. It explains that the task is to determine the lengt
# Intuition\n\nPalindrome is - a word that reads the same when read from **left** to **right** and from right to left. It explains that the task is to determine the length of a palindrome that can be formed using a given string. The approach taken is to build the palindrome rather than searching for it. The passage notes that in all the palindromes given as examples, each letter appears an even number of times except for one letter, which appears an odd number of times in cases where the string length is odd.\n\n# Greedy Approach\nWe can create a counter of the string. key=occurrences If there are even occurrences for the given character, we simply add the number of occurrences to the result, as we can take all the letters. If there are odd occurrences for the given character, we add everything but 1 (take 4 out of 5). If we met atleast one odd occurrence, we should add +1 to our end result to maximize the possible palindrome that can be built.\n\n# Complexity\n- Time complexity:\nTime - O(n) as we iterate over the string 2 times. 1 to create the counter, and another to count the occurrences.\n\n\n- Space complexity:\nO(n)/O(1) the counter space. Technically since we are bound to only upper and lower English letters than it will be O(52). But for generic n input, the space complexity will be O(n).\n\n# Code\n```\nclass Solution:\n    def longestPalindrome(self, s: str) -> int:\n        s_counter = Counter(s)\n        # We take all even, and biggest odd\n        odd = 0\n        result = 0\n        for v in s_counter.values():\n            if v % 2 == 0: result += v\n            else:\n                odd = 1\n                result += (v-1) # We take all events and 1 left over\n        \n        return result + odd\n\n\n\n\n\n\n\n\n\n\n```
['Greedy', 'Python', 'Python3']