Start by counting occurrences of each two-letter word. Pair each word with its reversed counterpart to build mirrored segments. Handle words with identical letters separately, placing at most one in the palindrome center, ensuring maximum length construction with precise hash lookups and careful array iteration.
Problem Statement
You are given an array of strings words, where each word consists of exactly two lowercase English letters. Your task is to select some words and concatenate them in any order to form the longest possible palindrome. Each word can be used at most once.
Return the length of the longest palindrome that can be created. If no palindrome can be formed, return 0. Consider that a valid palindrome must mirror around its center, and pairing reversed words or placing a word with identical letters centrally maximizes length.
Examples
Example 1
Input: words = ["lc","cl","gg"]
Output: 6
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
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
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.
Solution Approach
Count Words Using a Hash Map
Iterate through words and store the frequency of each in a hash map. This allows O(1) lookup for reversed pairs. Identical-letter words require separate tracking for potential center placement.
Pair Reversed Words
For each word, check if its reverse exists in the hash map. Each valid pair contributes twice the word length to the palindrome. Decrement counts to avoid reuse, ensuring proper pairing to maximize mirrored segments.
Add Central Word if Available
After pairing, identify if any word with identical letters remains. Place at most one in the palindrome center to increase length by 2. This step ensures that the palindrome is as long as possible without breaking mirroring.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) due to single-pass word counting and pairing with hash lookups. Space complexity is O(n) for the hash map storing word frequencies, independent of palindrome construction.
What Interviewers Usually Probe
- Check if you can use a hash map to find reversed word pairs efficiently.
- Consider how identical-letter words might serve as the palindrome's center.
- Be prepared to discuss linear-time pairing versus brute-force concatenation.
Common Pitfalls or Variants
Common pitfalls
- Forgetting to decrement counts after pairing leads to overcounting words.
- Not handling identical-letter words for central placement reduces palindrome length.
- Assuming order of words matters; any order is valid for concatenation.
Follow-up variants
- Allow words of length three or more and analyze how center placement generalizes.
- Return the actual palindrome string instead of just its length.
- Count distinct palindrome arrangements instead of maximum length.
How GhostInterview Helps
- Automatically detects reversed word pairs using hash tables to maximize palindrome segments.
- Highlights central placement opportunities for identical-letter words.
- Provides step-by-step length calculation and identifies common off-by-one errors in pairing.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the primary strategy to solve Longest Palindrome by Concatenating Two Letter Words?
Use array scanning with a hash map to count word frequencies, pair each word with its reverse, and place at most one identical-letter word in the center.
Can a word be used more than once in forming the palindrome?
No, each word can be selected at most once. Pairing and central placement must respect this constraint.
Why are words with identical letters treated differently?
They can serve as the center of the palindrome, allowing maximal length without requiring a mirrored pair.
What is the time complexity of this solution?
The solution runs in O(n) time, scanning all words once and using hash lookups for reversed pairs.
What failure modes should I watch for in this problem?
Common failures include overcounting paired words, ignoring central identical-letter words, and assuming word order affects the palindrome.
Need direct help with Longest Palindrome by Concatenating Two Letter Words instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Longest Palindrome by Concatenating Two Letter Words from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
The problem focuses on maximizing the number of palindromes that can be formed from a given list of words through specific letter swaps.
Open problem page#1684 Count the Number of Consistent StringsCount the number of strings fully composed of allowed characters using array scanning and hash lookup for efficiency.
Open problem page#1481 Least Number of Unique Integers after K RemovalsFind the least number of unique integers after removing exactly k elements from an array using efficient frequency counting and greedy strategy.
Open problem page