Longest Palindrome by Concatenating Two Letter Words
MedPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through the list of words to find pairs of words that are reverses of each other (e.g., "ab" and "ba"). It uses a nested loop structure to compare each word with every other word. To avoid re-using words, a boolean used array tracks which words have been included in the palindrome. After finding all non-palindromic pairs, it makes a second pass to handle palindromic words (e.g., "gg") to form the center of the final palindrome.
Algorithm
- Initialize
length = 0and a boolean arrayusedof the same size aswords, all set tofalse. - Iterate through
wordswith an outer loop fromi = 0ton-1. - If
words[i]is already used, skip it. - Check if
words[i]is a palindrome (e.g., "gg"). If so, skip it for now; we'll handle these in a separate pass. - If
words[i]is not a palindrome (e.g., "lc"), find its reverse (e.g., "cl"). - Start an inner loop from
j = i + 1ton-1. - If
words[j]is not used and is the reverse ofwords[i], we've found a pair. - Add 4 to
length, mark bothwords[i]andwords[j]as used, and break the inner loop to find a pair for the next word. - After the nested loops, handle the palindromic words. Create a frequency map for all unused words that are palindromes.
- Iterate through this frequency map. For each palindromic word with count
c, add(c / 2) * 4tolength. If any palindromic word has an odd count, we can place one in the center, so we note that a center piece is available. - If a center piece is available, add 2 to the total
length. - Return
length.
Walkthrough
The algorithm works by first pairing up all non-palindromic words with their reverses. It uses a nested loop, where the outer loop picks a word words[i] and the inner loop searches for its reverse words[j] in the rest of the array. An auxiliary boolean array used is maintained to ensure each word is used at most once. For every pair found (e.g., "lc" and "cl"), the length of the palindrome is increased by 4, and both words are marked as used. After this O(N^2) process, a separate pass is made over the remaining (unused) words. The frequencies of the unused palindromic words (e.g., "gg") are counted. These are used to further extend the palindrome. Even counts of a palindromic word form pairs, and an odd count allows one to be placed in the center.
class Solution { public int longestPalindrome(String[] words) { int n = words.length; boolean[] used = new boolean[n]; int length = 0; // Handle non-palindromic pairs for (int i = 0; i < n; i++) { if (used[i] || words[i].charAt(0) == words[i].charAt(1)) { continue; } String reversed = "" + words[i].charAt(1) + words[i].charAt(0); for (int j = i + 1; j < n; j++) { if (!used[j] && words[j].equals(reversed)) { length += 4; used[i] = true; used[j] = true; break; } } } // Handle palindromic words java.util.Map<String, Integer> palindromeCounts = new java.util.HashMap<>(); for (int i = 0; i < n; i++) { if (!used[i] && words[i].charAt(0) == words[i].charAt(1)) { palindromeCounts.put(words[i], palindromeCounts.getOrDefault(words[i], 0) + 1); } } boolean centerAdded = false; for (int count : palindromeCounts.values()) { length += (count / 2) * 4; if (count % 2 == 1) { centerAdded = true; } } if (centerAdded) { length += 2; } return length; }}Complexity
Time
O(N^2) due to the nested loops for finding pairs, where N is the number of words.
Space
O(N) for the `used` array. The map for palindromes stores at most 26 unique words.
Trade-offs
Pros
Conceptually simple and easy to follow the logic.
Cons
Highly inefficient for large inputs due to its quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' error on most online judges for the given constraints.
A more efficient approach is to first count the occurrences of each word using a HashMap. This avoids the O(N^2) search for pairs. After counting, we can iterate through the unique words in the map to build the palindrome based on the counts of words and their reverses.
Algorithm
- Create a
HashMap<String, Integer>to store the frequency of each word in the input array. - Initialize
length = 0and a booleancenterFound = false. - Iterate through each
wordand itscountin the HashMap. - Case 1: The word is a palindrome (e.g., "gg").
- We can form
count / 2pairs. Each pair ("gg" ... "gg") adds 4 to the length. So, add(count / 2) * 4tolength. - If
countis odd, one "gg" is left over. This can be the center of our palindrome. We setcenterFound = true.
- We can form
- Case 2: The word is not a palindrome (e.g., "lc").
- Find its reverse (e.g., "cl").
- To avoid double-counting (processing "lc" and then "cl" again), we only consider pairs where the word is lexicographically smaller than its reverse.
- If the reverse word exists in the map, find the number of pairs we can form, which is
min(count of word, count of reverse_word). - Each pair adds 4 to the length. Add
min_count * 4tolength.
- After iterating through all unique words, if
centerFoundis true, it means we have an unused palindromic word that can be placed in the center. Add 2 to the finallength. - Return
length.
Walkthrough
This approach begins by populating a HashMap with the frequencies of all words in the input array. This takes linear time, O(N). Then, it iterates through the map's entries. For each word, it checks if it's a palindrome (e.g., "gg") or not (e.g., "lc").
- If
wordis a palindrome, we calculate how many pairs can be formed from its count (count / 2) and add(count / 2) * 4to the total length. If the count is odd, a single word is left over, which can be a potential center for the final palindrome. A flagcenterFoundis set to true in this case. - If
wordis not a palindrome, we find its reverse. To prevent double-counting, we only process the pair if the current word is lexicographically smaller than its reverse. We find the number of pairs we can form (min(count(word), count(reverse))) and addpairs * 4to the length. Finally, ifcenterFoundis true, we add 2 to the total length for the central word.
import java.util.HashMap;import java.util.Map; class Solution { public int longestPalindrome(String[] words) { Map<String, Integer> counts = new HashMap<>(); for (String word : words) { counts.put(word, counts.getOrDefault(word, 0) + 1); } int length = 0; boolean centerFound = false; for (Map.Entry<String, Integer> entry : counts.entrySet()) { String word = entry.getKey(); int count = entry.getValue(); if (word.charAt(0) == word.charAt(1)) { // Palindromic word length += (count / 2) * 4; if (count % 2 == 1) { centerFound = true; } } else if (word.charAt(0) < word.charAt(1)) { // Non-palindromic, check one direction String reversed = "" + word.charAt(1) + word.charAt(0); if (counts.containsKey(reversed)) { int reversedCount = counts.get(reversed); int pairs = Math.min(count, reversedCount); length += pairs * 4; } } } if (centerFound) { length += 2; } return length; }}Complexity
Time
O(N) where N is the number of words. Building the map takes O(N), and iterating through the unique words takes O(U), where U <= N.
Space
O(U) to store the frequency map, where U is the number of unique words. Since U is at most 676, this can be considered O(min(N, 676)).
Trade-offs
Pros
Significantly faster than the nested loop approach with a linear time complexity.
Efficient for large inputs and passes the given constraints.
Cons
Uses a HashMap which might have a slight overhead compared to a simple array due to hashing and potential collisions.
This is the most optimized approach. Since the words are composed of two lowercase English letters, the number of possible unique words is small and fixed (26 * 26 = 676). We can use a 2D array int[26][26] as a direct-access frequency map, which is faster than a HashMap. counts[i][j] stores the frequency of the word formed by the i-th and j-th letters of the alphabet.
Algorithm
- Initialize a 2D array
counts[26][26]with all zeros. - Iterate through the input
words. For eachword, increment the corresponding cell in thecountsarray. For a wordw, the cell iscounts[w.charAt(0)-'a'][w.charAt(1)-'a']. - Initialize
length = 0and a booleancenterFound = false. - Handle non-palindromic pairs: Iterate with
ifrom 0 to 25 andjfromi+1to 25. This ensures we consider each pair of distinct letters(i, j)only once.- Find the number of pairs for words
(char(i), char(j))and(char(j), char(i)). This ismin(counts[i][j], counts[j][i]). - Add
min_count * 4tolength.
- Find the number of pairs for words
- Handle palindromic words: Iterate with
ifrom 0 to 25.- Let
count = counts[i][i]. - Add
(count / 2) * 4tolength. - If
countis odd, it means we have a leftover palindromic word for the center. SetcenterFound = true.
- Let
- If
centerFoundis true, add 2 tolength. - Return
length.
Walkthrough
This approach leverages the constraint that words are made of two lowercase English letters. Instead of a generic HashMap, it uses a 26x26 integer array as a specialized frequency map. counts[i][j] stores the count of the word formed by the i-th and j-th letters. The first step is to iterate through the input words and populate this 2D array, which takes O(N) time.
After counting, the palindrome length is calculated by iterating through the counts array.
- For non-palindromic pairs (where
i != j), we iterateifrom 0 to 25 andjfromi+1to 25 to avoid double counting. The number of pairs formed by(i,j)and(j,i)ismin(counts[i][j], counts[j][i]), contributing4 * pairsto the length. - For palindromic words (where
i == j), we iterateifrom 0 to 25. The number of pairs iscounts[i][i] / 2, contributing(counts[i][i] / 2) * 4to the length. Ifcounts[i][i]is odd, a single word can be a center, so a flag is set. Finally, if a center was found, 2 is added to the total length.
class Solution { public int longestPalindrome(String[] words) { int[][] counts = new int[26][26]; for (String word : words) { counts[word.charAt(0) - 'a'][word.charAt(1) - 'a']++; } int length = 0; boolean centerFound = false; // Handle non-palindromic pairs for (int i = 0; i < 26; i++) { for (int j = i + 1; j < 26; j++) { int pairs = Math.min(counts[i][j], counts[j][i]); length += pairs * 4; } } // Handle palindromic words for (int i = 0; i < 26; i++) { int count = counts[i][i]; length += (count / 2) * 4; if (count % 2 == 1) { centerFound = true; } } if (centerFound) { length += 2; } return length; }}Complexity
Time
O(N + A^2), where N is the number of words and A is the alphabet size. Since A is a constant (26), the complexity is O(N).
Space
O(A^2) for the `counts` array, where A is the alphabet size (26). This is constant space, O(1).
Trade-offs
Pros
Most efficient in terms of both time and space.
Avoids HashMap overhead by using direct array indexing.
Uses constant extra space, as the array size is fixed and does not depend on the input size N.
Cons
The logic might be slightly less intuitive at first glance compared to using a HashMap with string keys.
Solutions
Solution
class Solution {public int longestPalindrome(String[] words) { Map<String, Integer> cnt = new HashMap<>(); for (var w : words) { cnt.put(w, cnt.getOrDefault(w, 0) + 1); } int ans = 0, x = 0; for (var e : cnt.entrySet()) { var k = e.getKey(); var rk = new StringBuilder(k).reverse().toString(); int v = e.getValue(); if (k.charAt(0) == k.charAt(1)) { x += v & 1; ans += v / 2 * 2 * 2; } else { ans += Math.min(v, cnt.getOrDefault(rk, 0)) * 2; } } ans += x > 0 ? 2 : 0; return ans; }}class Solution {public: int longestPalindrome(vector<string> &words) { unordered_map<string, int> cnt; for (auto &w : words) cnt[w]++; int ans = 0, x = 0; for (auto &[k, v] : cnt) { string rk = k; reverse(rk.begin(), rk.end()); if (k[0] == k[1]) { x += v & 1; ans += v / 2 * 2 * 2; } else if (cnt.count(rk)) { ans += min(v, cnt[rk]) * 2; } } ans += x ? 2 : 0; return ans; }};class Solution: def longestPalindrome(self, words: List[str]) -> int: cnt = Counter(words) ans = x = 0 for k, v in cnt . items(): if k[0] == k[1]: x += v & 1 ans += v // 2 * 2 * 2 else: ans += min(v, cnt[k[:: - 1]]) * 2 ans += 2 if x else 0 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.