unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 409: Longest Palindrome

link

We can have at most one character with odd number of occurrences in a palindrome. So, in one pass we find the count of characters that appear odd number of times.

Time: \mathcal{O}(n), space: \mathcal{O}(\texttt{alphabet-size}).

class Solution:
    def longestPalindrome(self, s: str) -> int:
        odd_char_count = 0
        char_count = {}
        for c in s:
            if c not in char_count:
                char_count[c] = 1
                odd_char_count += 1
            else:
                char_count[c] += 1
                odd_char_count += (1 if char_count[c] % 2 == 1 else -1)
        
        delete_count = max(0, odd_char_count-1)
        return len(s) - delete_count

tanvirdotzaman

,

Leave a comment