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.The key observation in #2131 Longest Palindrome by Concatenating Two Letter Words is that each word has exactly two characters, which makes pairing strategies easier to reason about. A palindrome can be formed when a word like ab is matched with its reverse ba. To efficiently track such pairs, a hash table can be used to count occurrences of each word.
While iterating through the list, try to pair each word with its reverse to contribute four characters to the palindrome. Special attention is required for words where both characters are the same, such as aa. These can pair with each other, and at most one unpaired symmetric word can be placed in the center of the palindrome.
This approach combines greedy pairing with frequency counting to maximize the total palindrome length. Since each word is processed once and hash lookups are constant time, the algorithm runs in O(n) time with O(n) space for counting.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map + Greedy Pairing | O(n) | O(n) |
| Frequency Counting with Reverse Matching | O(n) | O(n) |
Bro Coders
Use these hints if you're stuck. Try solving on your own first.
A palindrome must be mirrored over the center. Suppose we have a palindrome. If we prepend the word "ab" on the left, what must we append on the right to keep it a palindrome?
We must append "ba" on the right. The number of times we can do this is the minimum of (occurrences of "ab") and (occurrences of "ba").
For words that are already palindromes, e.g. "aa", we can prepend and append these in pairs as described in the previous hint. We can also use exactly one in the middle to form an even longer palindrome.
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.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storage of words and their counts.
1#include <iostream>
2#include <unordered_map>
3using namespace std;
4
5int longestPalindrome(vector<string>& words) {
6 unordered_map<string, int> freq;
7 int length = 0, middleUsed = 0;
8
9 // Fill the map with word counts
10 for (const auto& word : words) {
11 freq[word]++;
12 }
13
14 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;
}
Using C++, we organize the problem by hashing word counts in an unordered_map, leveraging reversals to find palindrome-forming pairs. Self-mirrored words use a specific mechanism to determine if a middle can be formed in a longer palindrome.
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.
Time Complexity: O(n) with a constant factor given by alphabets.
Space Complexity: O(1) as the 26x26 map is constant in size.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Words with identical characters such as 'aa' are already palindromic. They can pair with another identical word to contribute to both halves of the palindrome, and if one remains unpaired, it can be placed in the center to maximize the total length.
Yes, variations of this problem appear in technical interviews at companies like Amazon, Google, and Meta. It tests understanding of hash maps, greedy strategies, and string manipulation under optimal time complexity.
A hash table (or dictionary) is the most suitable data structure for this problem. It allows constant-time lookups to check whether the reverse of a word exists and helps track the frequency of each two-letter string efficiently.
The optimal approach uses a hash map to count each two-letter word and greedily match it with its reverse. Pairs like 'ab' and 'ba' contribute to the palindrome length, while symmetric words like 'aa' may form pairs or serve as a center. This ensures an O(n) time solution.
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.