unreasonably effective

link

From palindrome’s mirror symmetry point of view, there are two types of elements:

1. Repeated: Two characters in the element are same like "gg".
   • If there are such elements, they can all be included, because a "gg" on the left half would have a "gg" on the right half.
   • If there are such elements, of them can be put in the two halves and the remaining one can be put in the center of the palindrome.
2. Not repeated: Two characters in the element are different like "lc".
   • It cannot be the center of the palindrome.
   • Only way to include them in the palindrome is if the mirror element like "cl" also exist. Then "lc" in the left half will have "cl" in the right half.

We find the longest length in two passes: (1) Build {element -> count} map (2) Depending on if it is a “repeated” element or not, we include them appropriately.

If there are elements, time: , space: .

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        counts = {}
        for e in words:
            counts[e] = counts.get(e, 0) + 1
        
        ll = 0
        center = None
        for e, m in counts.items():
            is_repeated = (e[0] == e[1])
            
            if is_repeated:
                q, r = divmod(m, 2)
                ll += 4*q
                if not center and r == 1:
                    ll += 2
                    center = e
            else:
                mirror = f"{e[1]}{e[0]}"
                if mirror not in counts:
                    continue
                
                ll += 4*min( m, counts[mirror] )
                counts[e] = 0
            
        return ll