Skip to main content
Talentd

Longest Palindrome by Concatenating Two Letter Words - Solution & Explanation

MediumArrayHash TableStringGreedy21 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

You are given an array of strings words. Each element of words consists of two lowercase English letters.

Create the longest possible palindrome by selecting some elements from words and concatenating them in any order. Each element can be selected at most once.

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.

A palindrome is a string that reads the same forward and backward.

 

Example 1:

Input: words = ["lc","cl","gg"]
Output: 6
Explanation: One longest palindrome is "lc" + "gg" + "cl" = "lcggcl", of length 6.
Note that "clgglc" is another longest palindrome that can be created.

Example 2:

Input: words = ["ab","ty","yt","lc","cl","ab"]
Output: 8
Explanation: One longest palindrome is "ty" + "lc" + "cl" + "yt" = "tylcclyt", of length 8.
Note that "lcyttycl" is another longest palindrome that can be created.

Example 3:

Input: words = ["cc","ll","xx"]
Output: 2
Explanation: One longest palindrome is "cc", of length 2.
Note that "ll" is another longest palindrome that can be created, and so is "xx".

 

Constraints:

  • 1 <= words.length <= 105
  • words[i].length == 2
  • words[i] consists of lowercase English letters.

Approach Overview

Problem Overview: You receive an array of two‑letter strings. You may concatenate selected words in any order, but each word can be used once. The goal is to build the longest possible palindrome string. Because every word has exactly two characters, the structure of the palindrome depends on pairing words with their reversed counterpart.

Approach 1: Greedy Pair Matching (O(n) time, O(n) space)

This approach counts how many times each two‑letter word appears using a hash map. While iterating through the array, check whether the reverse of the current word already exists in the map. If it does, you form a palindrome segment of length 4 (for example "ab" + "ba"). Decrease the stored count and add 4 to the result. Words where both characters are the same (like "aa" or "cc") require special handling: they can pair with another identical word to contribute 4 characters, but a single leftover symmetric word can sit in the middle of the palindrome and contribute 2 characters.

The greedy idea works because pairing reversed words always increases the palindrome length without affecting other combinations. A frequency map guarantees O(1) lookups while scanning the array once. This method relies heavily on hash table counting and a small amount of greedy reasoning to place pairs and optionally one center element.

Approach 2: String Reversal and Hash (O(n) time, O(n) space)

Another perspective is to treat every word and explicitly check its reversed form. Insert each word into a hash map that tracks unused occurrences. For a given word w, compute reverse(w). If the reversed word exists in the map with available frequency, pair them and increase the palindrome length by 4. Otherwise, store the current word for a potential future match.

Symmetric words like "gg" are handled by pairing identical entries from the map. After processing all words, if any symmetric word still has a remaining count, one of them can be placed in the center of the palindrome, contributing 2 characters. The algorithm is still a single pass with constant‑time hash operations. It highlights the importance of fast reverse lookups using string manipulation and frequency counting.

Recommended for interviews: The greedy pair matching solution is what most interviewers expect. It demonstrates that you recognize the palindrome structure and exploit the fixed two‑character word length. Showing the counting logic first proves you understand the pairing rules, while the optimized hash map implementation confirms you can reduce the problem to an O(n) scan using efficient lookups.

Approach 1: Greedy Pair Matching

The first approach involves counting occurrences of each word and its reverse. If a word appears with its reverse, they can be directly paired to contribute to the palindrome length. Symmetrical words like 'gg' can be used optimally to form palindromes, with one potentially serving as a center if their count is odd.

The C solution uses a manual structure to count word occurrences and then utilizes sorting and dual iterations to pair words and compute maximum palindrome length. Reversals are computed for each word, ensuring that all possible pairs contribute optimally to the palindrome length.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storage of words and their counts.

Try this approach in the editor →

Approach 2: String Reversal and Hash

This approach involves creating a hash map to quickly check for the existence of a word's reverse in the input, allowing us to efficiently pair words or use symmetric words optimally. We calculate pairs and handle middle contributions by taking account of unsused symmetric words.

This C solution employs a two-dimensional array approach (map) to store the frequency of character pairs. It counts how many of each type of word pair exist and checks for their reversal, adding contributions to the length based on pair formation. It separately checks for symmetrical pairs to add potential middle characters.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) with a constant factor given by alphabets.
Space Complexity: O(1) as the 26x26 map is constant in size.

Try this approach in the editor →

Approach 3: Greedy + Hash Table

First, we use a hash table cnt to count the occurrences of each word.

Iterate through each word k and its count v in cnt:

  • If the two letters in k are the same, we can concatenate \left \lfloor \frac{v}{2} \right \rfloor times 2 copies of k to the front and back of the palindrome. If there is one k left, we can record it in x for now.

  • If the two letters in k are different, we need to find a word k' such that the two letters in k' are the reverse of k, i.e., k' = k[1] + k[0]. If k' exists, we can concatenate min(v, cnt[k']) copies of k to the front and back of the palindrome.

After the iteration, if x is not empty, we can also place one word in the middle of the palindrome.

The time complexity is O(n), and the space complexity is O(n), where n is the number of words.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Pair Matching

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storage of words and their counts.

String Reversal and Hash

Time Complexity: O(n) with a constant factor given by alphabets.
Space Complexity: O(1) as the 26x26 map is constant in size.

Greedy + Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Pair Matching with Frequency MapO(n)O(n)Best general solution. Single pass with hash counting and greedy pairing.
String Reversal and Hash LookupO(n)O(n)Good when emphasizing reverse string matching and explicit pair detection.

Video Solution

Longest Palindrome by Concatenating Two Letter Words | Simple Way | Leetcode 2131 | codestorywithMIK • codestorywithMIK • 9,906 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Longest Palindrome by Concatenating Two Letter Words easy or hard?
The problem is rated Medium because the idea is simple but requires careful handling of symmetric words like "aa". Candidates must recognize that reversed pairs build the palindrome edges while at most one identical pair can occupy the center.
Longest Palindrome by Concatenating Two Letter Words Python/Java solution
Python, Java, C++, and JavaScript implementations typically use a dictionary or HashMap to track counts. During iteration, the algorithm checks the reversed string and updates the palindrome length accordingly. The final complexity remains O(n) time and O(n) space across languages.
How to solve Longest Palindrome by Concatenating Two Letter Words in O(n)?
Store counts of each two‑letter word in a hash map. For every word, check if its reversed version already exists. If it does, form a pair and add 4 to the palindrome length. After processing all words, check if one symmetric word like "aa" remains to place in the center, adding 2 more characters.
What is the best approach for Longest Palindrome by Concatenating Two Letter Words?
The optimal approach uses greedy pair matching with a hash map. Count occurrences of each two‑letter word and match it with its reversed counterpart (for example "ab" with "ba"). Each pair contributes 4 characters to the palindrome. Words with identical characters like "aa" can form pairs or act as a single center element.
Is Longest Palindrome by Concatenating Two Letter Words asked at Google/Amazon/Meta?
Palindrome construction and hash‑based pairing problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variations of this question test string manipulation, greedy reasoning, and efficient hash table usage.
What data structure is used in Longest Palindrome by Concatenating Two Letter Words?
The core data structure is a hash map (or dictionary) used to count word frequencies and perform O(1) reverse lookups. This allows quick pairing between a word and its reversed counterpart while scanning the array.
What is the time complexity of Longest Palindrome by Concatenating Two Letter Words?
The optimal solution runs in O(n) time where n is the number of words. Each word is processed once, and hash map lookups for reversed strings take O(1) on average. Space complexity is O(n) to store word frequencies.

Ready to solve this problem?

Practice Longest Palindrome by Concatenating Two Letter Words with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindrome

Next

Palindrome Pairs