Watch 10 video solutions for Longest Palindrome by Concatenating Two Letter Words, a medium level problem involving Array, Hash Table, String. This walkthrough by codestorywithMIK has 9,543 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |