LeetCode 2131 - Longest Palindrome by Concatenating Two Letter Words

LeetCode Problem 2131

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Greedy, Counting

Solution

Problem Understanding

This problem asks us to construct the longest possible palindrome using a list of two-letter words. Each word can be used at most once, and the order of concatenation can be chosen freely. A palindrome reads the same forwards and backwards, which means that for a word pair to appear symmetrically around the center, one word must be the reverse of the other. Additionally, words that are already palindromes themselves (like "gg" or "cc") can appear in the middle or as mirrored pairs on either side.

The input is an array of strings words, where each string is exactly two lowercase letters. The output is the total length of the palindrome formed, which is simply the sum of lengths of the words used. Constraints indicate that the list can have up to 100,000 words, which rules out naive brute-force attempts like generating all permutations.

Important edge cases include:

1. Words that are already palindromes (like "aa") can be used in the middle of the palindrome.
2. Words that have no reverse counterpart in the list cannot be used symmetrically.
3. Multiple identical palindromic words (like ["cc","cc","cc"]) may allow only one in the middle but can pair the others on sides.

Understanding these constraints and properties allows us to design an efficient solution using a hash map.

Approaches

Brute-force approach would involve generating all permutations of the words and checking each concatenation for palindrome validity. This is correct but infeasible because for n = 10^5 words, the number of permutations is astronomically large, making it impossible to compute in reasonable time.

The key insight is that a palindrome can be constructed by pairing words with their reversed counterparts. We only need to count the occurrences of each word and check if its reverse exists. For words that are palindromes themselves, we can use an even number of them to form mirrored pairs, and possibly place a single one in the middle if no other middle word exists.

This reduces the problem to hash table counting, which allows us to compute the longest palindrome in linear time with respect to the number of words.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n!)	Generate all permutations and check each for palindrome, infeasible for large n
Optimal	O(n)	O(n)	Use hash map to count words and pair each word with its reverse efficiently

Algorithm Walkthrough

1. Initialize a hash map count to store the frequency of each word in words.
2. Initialize a variable length to keep track of the total palindrome length.
3. Initialize a boolean flag used_middle to indicate whether a central palindromic word has been used.
4. Iterate over each unique word w in the hash map.
5. Check if w is a palindrome itself (i.e., w[0] == w[1]). If so:

• Add 2 * (count[w] // 2) * 2 to length for mirrored pairs (each word contributes 2 letters).
• If there is an odd count of w and used_middle is False, add 2 to length for the central word and set used_middle to True.

6. If w is not a palindrome, compute its reverse rev.

• If rev exists in the hash map, add 2 * 2 * min(count[w], count[rev]) to length (each pair contributes 4 letters).
• Mark both w and rev as processed by setting their counts to zero to avoid double counting.

7. After iterating all words, return length.

Why it works: Every valid pair is counted exactly once, and a single palindromic word can serve as the center. This ensures that the resulting string is the longest possible palindrome.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        count = Counter(words)
        length = 0
        used_middle = False
        
        for word in list(count.keys()):
            if count[word] == 0:
                continue
            rev = word[::-1]
            if word == rev:
                pairs = count[word] // 2
                length += pairs * 4
                if count[word] % 2 == 1 and not used_middle:
                    length += 2
                    used_middle = True
                count[word] = 0
            elif rev in count:
                pairs = min(count[word], count[rev])
                length += pairs * 4
                count[word] -= pairs
                count[rev] -= pairs
        
        return length

This code first counts the frequency of each word, then iterates through each word to find either mirrored pairs or palindromic words for the center. Each word is processed exactly once, ensuring correctness and efficiency.

Go Solution

func longestPalindrome(words []string) int {
    count := make(map[string]int)
    for _, word := range words {
        count[word]++
    }

    length := 0
    usedMiddle := false

    for word, c := range count {
        if c == 0 {
            continue
        }
        rev := string([]byte{word[1], word[0]})
        if word[0] == word[1] {
            pairs := c / 2
            length += pairs * 4
            if c%2 == 1 && !usedMiddle {
                length += 2
                usedMiddle = true
            }
            count[word] = 0
        } else if count[rev] > 0 {
            pairs := min(c, count[rev])
            length += pairs * 4
            count[word] -= pairs
            count[rev] -= pairs
        }
    }
    
    return length
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

The Go solution mirrors the Python logic with minor language differences, including explicit byte slicing for reversing two-character strings and a helper min function.

Worked Examples

Example 1: ["lc","cl","gg"]

Word	Count	Action	Length
lc	1	rev = cl exists, pair -> add 4	4
cl	1	already paired	4
gg	1	palindromic, add 2 for middle	6

Result: 6

Example 2: ["ab","ty","yt","lc","cl","ab"]

Word	Count	Action	Length
ab	2	rev = ba not exists, palindromic? no	0
ty	1	rev = yt exists, pair -> add 4	4
yt	1	paired	4
lc	1	rev = cl exists, pair -> add 4	8
cl	1	paired	8
ab	2	nothing	8

Result: 8

Example 3: ["cc","ll","xx"]

Word	Count	Action	Length
cc	1	palindromic, add 2	2
ll	1	palindromic, skipped	2
xx	1	palindromic, skipped	2

Result: 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate through the list once to count words and once through unique words to pair them.
Space	O(n)	Hash map stores counts of each unique word, at most 26*26 = 676 entries, which is bounded but asymptotically O(n).

The algorithm scales linearly with input size and uses extra space proportional to the number of unique words.

Test Cases

# Provided examples
assert Solution().longestPalindrome(["lc","cl","gg"]) == 6  # basic palindrome with central word
assert Solution().longestPalindrome(["ab","ty","yt","lc","cl","ab"]) == 8  # multiple pairs
assert Solution().longestPalindrome(["cc","ll","xx"]) == 2  # only one palindromic word used

# Edge cases
assert Solution().longestPalindrome(["aa"]) == 2  # single palindromic word
assert Solution().longestPalindrome(["ab","ba"]) == 4  # single pair forming palindrome
assert Solution().longestPalindrome(["ab","cd"]) == 0  # no palindromes possible
assert Solution().longestPalindrome(["aa","aa","aa"]) == 6  # multiple palindromes with central use
assert Solution().longestPalindrome(["ab","ba","cc","cc","cc"]) == 10  # mix of mirrored pairs and center

Test	Why
["lc","cl","gg"]	Valid palindrome with central word
["ab","ty","yt","lc","cl","ab"]	Multiple mirrored pairs
["cc","ll","xx"]	Only one palindromic word used
["aa"]	Single palindromic word edge case