Longest Palindrome by Concatenating Two Letter Words solution and explanation
Google
9 more videos on this problem
Longest Palindrome by Concatenating Two Letter Words | Simple Way | Leetcode 2131 | codestorywithMIKcodestorywithMIK · 17:35 · 9K views
2131. Longest Palindrome by Concatenating Two Letter Words (Leetcode Medium)Programming Live with Larry · 13:18 · 1K views
Longest Palindrome by Concatenating Two Letter Words | Leetcode 2131Techdose · 23:32 · 1K views
2131. Longest Palindrome by Concatenating Two Letter Words || DSA || Leetcode Daily Challenge ||Leetcode Daily Challenge · 8:34 · 1K views
Longest Palindrome by Concatenating Two Letter Words - Leetcode 2131 - PythonTim Huang · 5:14 · 733 views
Explaining Leetcode - #2131 Longest Palindrome by Concatenating Two Letter Words (Medium)JTECH · 22:20 · 619 views
2131. Longest Palindrome by Concatenating Two Letter Words | Leetcode Daily - PythonLeetcode Daily · 6:25 · 515 views
2131. Longest Palindrome by Concatenating Two Letter Words | JavaScript | LeetCode Daily ChallengeLeetCodeWithMonu · 14:21 · 347 views
2131. Longest Palindrome by Concatenating Two Letter Words || Leetcode || C++Code with Sky · 12:22 · 263 views
2131. Longest Palindrome by Concatenating Two Letter Words | Leetcode | PythonJobless Engineer · 10:21 · 233 views
The problem
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.
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.
from collections import Counter
class Solution:
def longestPalindrome(self, words):
count = Counter(words)
length = 0
middle_used = False
for word, cnt in count.items():
rev = word[::-1]
if word == rev: # Symmetric word like 'gg'
length += (cnt // 2) * 4
if cnt % 2 == 1 and not middle_used:
length += 2
middle_used = True
elif rev in count:
pairs = min(cnt, count[rev])
length += pairs * 4
count[rev] = 0 # Mark reverse used
return length
# Example usage:
sol = Solution()
words = ["lc", "cl", "gg"]
print(sol.longestPalindrome(words))import java.util.HashMap;
class Solution {
public int longestPalindrome(String[] words) {
HashMap<String, Integer> map = new HashMap<>();
int length = 0;
boolean midUsed = false;
for (String word : words) {
map.put(word, map.getOrDefault(word, 0) + 1);
}
for (String word : map.keySet()) {
int count = map.get(word);
String reverse = new StringBuilder(word).reverse().toString();
if (word.equals(reverse)) { // Symmetrical
length += (count / 2) * 4;
if (count % 2 == 1 && !midUsed) {
length += 2;
midUsed = true;
}
} else if (map.containsKey(reverse)) {
int minPairs = Math.min(count, map.get(reverse));
length += minPairs * 4;
map.put(reverse, 0); // Mark reverse used
}
}
return length;
}
public static void main(String[] args) {
Solution sol = new Solution();
String[] words = {"lc", "cl", "gg"};
System.out.println(sol.longestPalindrome(words));
}
}#include <iostream>
#include <unordered_map>
using namespace std;
int longestPalindrome(vector<string>& words) {
unordered_map<string, int> freq;
int length = 0, middleUsed = 0;
// Fill the map with word counts
for (const auto& word : words) {
freq[word]++;
}
for (auto& [word, count] : freq) {
string rev = string(1, word[1]) + word[0];
if (word == rev) { // Self-mirrored like "gg"
length += (count / 2) * 4;
if (count % 2 == 1 && !middleUsed) {
length += 2;
middleUsed = 1;
}
} else if (freq.find(rev) != freq.end()) {
int pairs = min(count, freq[rev]);
length += pairs * 4;
freq[rev] = 0; // Mark used
}
}
return length;
}
int main() {
vector<string> words = {"lc", "cl", "gg"};
cout << longestPalindrome(words) << endl;
return 0;
}function longestPalindrome(words) {
const count = {};
let length = 0;
let middleUsed = false;
for (let word of words) {
count[word] = (count[word] || 0) + 1;
}
for (let word of Object.keys(count)) {
let rev = word[1] + word[0];
if (word === rev) { // Symmetric word
length += Math.floor(count[word] / 2) * 4;
if (count[word] % 2 === 1 && !middleUsed) {
length += 2;
middleUsed = true;
}
} else if (count[rev]) {
let pairs = Math.min(count[word], count[rev]);
length += pairs * 4;
delete count[rev]; // Mark reverse used
}
}
return length;
}
// Example usage:
const words = ["lc", "cl", "gg"];
console.log(longestPalindrome(words));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_WORDS 100000
typedef struct {
char word[3];
int count;
} WordCount;
// Comparator for qsort
int cmp(const void *a, const void *b) {
return strcmp(((WordCount *)a)->word, ((WordCount *)b)->word);
}
int longestPalindrome(char **words, int wordsSize) {
WordCount map[MAX_WORDS];
int mapSize = 0;
int length = 0, middleUsed = 0;
// Fill the map with word counts
for (int i = 0; i < wordsSize; ++i) {
int j;
for (j = 0; j < mapSize; ++j) {
if (strcmp(map[j].word, words[i]) == 0) {
map[j].count++;
break;
}
}
if (j == mapSize) {
strcpy(map[mapSize].word, words[i]);
map[mapSize++].count = 1;
}
}
qsort(map, mapSize, sizeof(WordCount), cmp);
for (int i = 0; i < mapSize; ++i) {
char reversed[3];
reversed[0] = map[i].word[1];
reversed[1] = map[i].word[0];
reversed[2] = '\0';
if (strcmp(map[i].word, reversed) == 0) { // cases like "gg"
length += (map[i].count / 2) * 4;
if (map[i].count % 2 != 0 && !middleUsed) {
length += 2;
middleUsed = 1;
}
} else {
for (int j = i + 1; j < mapSize; ++j) {
if (strcmp(map[j].word, reversed) == 0) {
length += 4 * (map[i].count < map[j].count ? map[i].count : map[j].count);
map[j].count = 0; // Mark used
break;
}
}
}
}
return length;
}
int main() {
char *words[] = {"lc", "cl", "gg"};
int wordsSize = 3;
printf("%d", longestPalindrome(words, wordsSize));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int LongestPalindrome(string[] words) {
var dict = new Dictionary<string, int>();
int length = 0;
bool middleUsed = false;
foreach (var word in words) {
if (!dict.ContainsKey(word)) {
dict[word] = 0;
}
dict[word]++;
}
foreach (var kv in dict) {
string word = kv.Key;
int count = kv.Value;
string revWord = new string(new char[] { word[1], word[0] });
if (word == revWord) { // Symmetric word
length += (count / 2) * 4;
if (count % 2 == 1 && !middleUsed) {
length += 2;
middleUsed = true;
}
} else if (dict.ContainsKey(revWord)) {
int pairs = Math.Min(count, dict[revWord]);
length += pairs * 4;
dict[revWord] = 0; // Mark reverse used
}
}
return length;
}
public static void Main(string[] args) {
Solution sol = new Solution();
string[] words = new string[] { "lc", "cl", "gg" };
Console.WriteLine(sol.LongestPalindrome(words));
}
}The Python solution leverages the `Counter` class for counting words efficiently. It checks each word and its reverse to determine the optimal contributions to the possible palindrome formation. Special attention is given to self-reversing words like 'gg' for potential middle use.
Time Complexity: O(n) due to counter operations.
Space Complexity: O(n) for the Counter dictionary.
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.
class Solution:
def longestPalindrome(self, words):
count = [[0] * 26 for _ in range(26)]
length = 0
middle_used = False
for word in words:
a, b = ord(word[0]) - ord('a'), ord(word[1]) - ord('a')
if count[b][a] > 0:
length += 4
count[b][a] -= 1
else:
count[a][b] += 1
for i in range(26):
if count[i][i] > 0:
middle_used = True
break
return length + (2 if middle_used else 0)
# Example usage:
sol = Solution()
words = ["lc", "cl", "gg"]
print(sol.longestPalindrome(words))class Solution {
public int longestPalindrome(String[] words) {
int[][] map = new int[26][26];
int length = 0;
boolean hasMiddle = false;
for (String word : words) {
int a = word.charAt(0) - 'a';
int b = word.charAt(1) - 'a';
if (map[b][a] > 0) {
length += 4;
map[b][a]--;
} else {
map[a][b]++;
}
}
for (int i = 0; i < 26; ++i) {
if (map[i][i] > 0) {
hasMiddle = true;
break;
}
}
return length + (hasMiddle ? 2 : 0);
}
public static void main(String[] args) {
Solution sol = new Solution();
String[] words = {"lc", "cl", "gg"};
System.out.println(sol.longestPalindrome(words));
}
}#include <iostream>
#include <vector>
using namespace std;
int longestPalindrome(vector<string>& words) {
int map[26][26] = {0};
int length = 0;
int symmetricCount = 0;
for (const string& word : words) {
int first = word[0] - 'a';
int second = word[1] - 'a';
if (map[second][first] > 0) {
length += 4;
map[second][first]--;
} else {
map[first][second]++;
}
}
for (int i = 0; i < 26; ++i) {
if (map[i][i] > 0) {
symmetricCount = 1;
break;
}
}
return length + symmetricCount * 2;
}
int main() {
vector<string> words = {"lc", "cl", "gg"};
cout << longestPalindrome(words) << endl;
return 0;
}function longestPalindrome(words) {
const map = Array.from({length: 26}, () => Array(26).fill(0));
let length = 0;
let middleUsed = false;
for (const word of words) {
const a = word.charCodeAt(0) - 97;
const b = word.charCodeAt(1) - 97;
if (map[b][a] > 0) {
length += 4;
map[b][a]--;
} else {
map[a][b]++;
}
}
for (let i = 0; i < 26; i++) {
if (map[i][i] > 0) {
middleUsed = true;
break;
}
}
return length + (middleUsed ? 2 : 0);
}
// Example usage:
const words = ["lc", "cl", "gg"];
console.log(longestPalindrome(words));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int longestPalindrome(char** words, int wordsSize) {
int map[26][26] = {0};
int length = 0;
int symmetricCount = 0;
for (int i = 0; i < wordsSize; ++i) {
int first = words[i][0] - 'a';
int second = words[i][1] - 'a';
if (map[second][first] > 0) {
length += 4;
map[second][first]--;
} else {
map[first][second]++;
}
}
for (int i = 0; i < 26; ++i) {
if (map[i][i] > 0) {
symmetricCount = 1;
break;
}
}
return length + symmetricCount * 2;
}
int main() {
char* words[] = { "lc", "cl", "gg" };
int wordsSize = sizeof(words) / sizeof(words[0]);
printf("%d", longestPalindrome(words, wordsSize));
return 0;
}using System;
public class Solution {
public int LongestPalindrome(string[] words) {
int[,] map = new int[26, 26];
int length = 0;
bool hasMiddle = false;
foreach (var word in words) {
int a = word[0] - 'a';
int b = word[1] - 'a';
if (map[b, a] > 0) {
length += 4;
map[b, a]--;
} else {
map[a, b]++;
}
}
for (int i = 0; i < 26; ++i) {
if (map[i, i] > 0) {
hasMiddle = true;
break;
}
}
return length + (hasMiddle ? 2 : 0);
}
public static void Main(string[] args) {
Solution sol = new Solution();
string[] words = { "lc", "cl", "gg" };
Console.WriteLine(sol.LongestPalindrome(words));
}
}In Python, symbol counting across combined alphabets supports identifying palindrome pairs, with a focus on O(1) checks in the two-dimensional count list. It detects symmetry with conditional logic for central placement.
Time Complexity: O(n), list operations are efficiently managed.
Space Complexity: O(1), list size is bounded to a fixed 26x26.
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
kare the same, we can concatenate\left \lfloor \frac{v}{2} \right \rfloor times 2copies ofkto the front and back of the palindrome. If there is onekleft, we can record it inxfor now. -
If the two letters in
kare different, we need to find a wordk'such that the two letters ink'are the reverse ofk, i.e.,k' = k[1] + k[0]. Ifk'exists, we can concatenatemin(v, cnt[k'])copies ofkto 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.
function longestPalindrome(words: string[]): number {
const cnt = new Map<string, number>();
for (const w of words) cnt.set(w, (cnt.get(w) || 0) + 1);
let [ans, x] = [0, 0];
for (const [k, v] of cnt.entries()) {
if (k[0] === k[1]) {
x += v & 1;
ans += Math.floor(v / 2) * 2 * 2;
} else {
ans += Math.min(v, cnt.get(k[1] + k[0]) || 0) * 2;
}
}
ans += x ? 2 : 0;
return ans;
}func longestPalindrome(words []string) int {
cnt := map[string]int{}
for _, w := range words {
cnt[w]++
}
ans, x := 0, 0
for k, v := range cnt {
if k[0] == k[1] {
x += v & 1
ans += v / 2 * 2 * 2
} else {
rk := string([]byte{k[1], k[0]})
if y, ok := cnt[rk]; ok {
ans += min(v, y) * 2
}
}
}
if x > 0 {
ans += 2
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Pair Matching | Time Complexity: O(n) due to counter operations. |
| String Reversal and Hash | Time Complexity: O(n), list operations are efficiently managed. |
| Greedy + Hash Table | – |
Complexity analysis
| 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. |
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.