Longest Palindrome by Concatenating Two Letter Words

main.md

Question

Approach

I use a Counter to count occurrences of each word. For non-palindromic words (like "ab" and "ba"), I find the matching reverse pairs and count the minimum between them. For palindromic words (like "gg", "cc"), I use pairs and reserve one (if available) for the center of the palindrome. Each pair contributes 4 characters (2 + 2), and the center adds 2.

Implementation

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        count = Counter(words)
        length = 0
        central_used = False

        for word in count:
            reversed_word = word[::-1]
            if word == reversed_word:
                pairs = count[word] // 2
                length += pairs * 4
                if count[word] % 2 == 1:
                    central_used = True
            elif reversed_word in count:
                pairs = min(count[word], count[reversed_word])
                length += pairs * 4
                count[reversed_word] = 0

        if central_used:
            length += 2

        return length

Complexities

• Time: O(n)
• Space: O(n)