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 <= 105words[i].length == 2words[i] consists of lowercase English letters.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.
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.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storage of words and their counts.
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.
Time Complexity: O(n) with a constant factor given by alphabets.
Space Complexity: O(1) as the 26x26 map is constant in size.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Pair Matching | Time Complexity: O(n log n) due to sorting. |
| String Reversal and Hash | Time Complexity: O(n) with a constant factor given by alphabets. |
| Greedy + Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Pair Matching with Frequency Map | O(n) | O(n) | Best general solution. Single pass with hash counting and greedy pairing. |
| String Reversal and Hash Lookup | O(n) | O(n) | Good when emphasizing reverse string matching and explicit pair detection. |
Longest Palindrome by Concatenating Two Letter Words | Simple Way | Leetcode 2131 | codestorywithMIK • codestorywithMIK • 9,543 views views
Watch 9 more video solutions →Practice Longest Palindrome by Concatenating Two Letter Words with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor