Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A two-letter word on one side of a palindrome needs its reversal on the other side. Each matched pair contributes four characters. At the center, at most one unmatched word with identical letters can be used.

Approach

Maintain counts of unmatched words. For each word, consume an available reversed word and add four to the length; otherwise store the current word as unmatched. After the scan, add two if any unmatched double-letter word remains, then stop looking for a center. Return the total length. Matching reversals immediately is safe because a word has only one required partner type, and double-letter words are paired before reserving at most one for the middle.

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        map = defaultdict(int)
        res = 0

        for w in words:
            rev = w[1] + w[0]
            if map[rev]:
                res += 4
                map[rev] -= 1
            else:
                map[w] += 1

        for k in map:
            if k[0] == k[1] and map[k]:
                res += 2
                break

        return res

Complexity analysis

Let w = words.length and u be the number of distinct two-letter words. Time: O(w + u). Auxiliary space: O(u) for unmatched-word counts.