Longest Palindrome by Concatenating Two Letter Words Solution
Longest Palindrome by Concatenating Two Letter Words solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Longest Palindrome by Concatenating Two Letter Words is a medium coding problem on arrays, strings and hash table, asked in Amazon, Google, Microsoft and Databricks interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Hash Table, Greedy
- Asked at: Amazon, Google, Microsoft, Databricks
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array words; every word consists of exactly two lowercase letters.
Pick some of the words (each array element at most once) and concatenate them in any order you like to form a palindrome — a string that reads the same forwards and backwards.
Return the length of the longest palindrome you can build, or 0 if you cannot build any.
Example 1
Input: words = ["ka","ak","oo","oo","oo","co"]
Output: 10
Explanation: `"ka" + "oo" + "oo" + "oo" + "ak"` gives `"kaooooooak"`. `"co"` has no partner `"oc"`.
Example 2
Input: words = ["ab","cd","ef"]
Output: 0
Example 3
Input: words = ["xx"]
Output: 2
Explanation: A single word with two equal letters is a palindrome by itself.
Constraints
1 <= words.length <= 10^5words[i].length == 2words[i] consists of lowercase English letters
Hints for Longest Palindrome by Concatenating Two Letter Words
Hint 1
In a palindrome built from two-letter blocks, the block at position
ifrom the left mirrors the block at positionifrom the right.Hint 2
So a word
xywithx != ycan only be used together with a copy ofyx. A wordxxcan pair with anotherxx.Hint 3
Count the words. Pair
xywithyxas often as possible, pairxxwithxx, and if anyxxis left over, put one in the middle.
How to solve Longest Palindrome by Concatenating Two Letter Words
Words go in mirrored pairs around the centre: xy needs a yx, xx needs another xx. At most one unpaired xx can sit in the very middle.
Approach
- Count every word in a 26 × 26 table
cnt[x][y]. - For each pair of letters
x < y, add4 × min(cnt[x][y], cnt[y][x]). - For each letter
x, add4 × floor(cnt[x][x] / 2), and remember whether anycnt[x][x]is odd. - If some
xxword was left over, add 2 for the centre.
Why it works
Because every word has length 2 and the palindrome is a concatenation of words, the blocks align: the i-th word from the left is the reverse of the i-th word from the right, except possibly one word exactly in the middle, which must then be a palindrome itself (xx). Hence every usable word except the centre is matched with its reverse, the count of xy pairs is limited by the rarer of xy and yx, and greedily using all such pairs plus one spare xx is optimal.
Complexity
- Time —
O(n + 26²) - Space —
O(26²)
Pitfalls
- Only one leftover
xxcan be placed in the middle, even if several letters have odd counts. - Do not count an
xy/yxpair twice by visiting both orders — loop overx < yonly. - A word
xywithx != ycan never be the centre.
Reference solution
Python
from typing import List
def longestPalindrome(words: List[str]) -> int:
cnt = [[0] * 26 for _ in range(26)]
for w in words:
cnt[ord(w[0]) - 97][ord(w[1]) - 97] += 1
length = 0
center = False
for x in range(26):
length += (cnt[x][x] // 2) * 4
if cnt[x][x] % 2 == 1:
center = True
for y in range(x + 1, 26):
length += min(cnt[x][y], cnt[y][x]) * 4
return length + (2 if center else 0)Java
public static int longestPalindrome(String[] words) {
int[][] cnt = new int[26][26];
for (String w : words) cnt[w.charAt(0) - 'a'][w.charAt(1) - 'a']++;
int len = 0;
boolean center = false;
for (int x = 0; x < 26; x++) {
len += (cnt[x][x] / 2) * 4;
if (cnt[x][x] % 2 == 1) center = true;
for (int y = x + 1; y < 26; y++) len += Math.min(cnt[x][y], cnt[y][x]) * 4;
}
return len + (center ? 2 : 0);
}C++
int longestPalindrome(vector<string>& words) {
int cnt[26][26] = {{0}};
for (auto& w : words) cnt[w[0] - 'a'][w[1] - 'a']++;
int len = 0;
bool center = false;
for (int x = 0; x < 26; x++) {
len += (cnt[x][x] / 2) * 4;
if (cnt[x][x] % 2 == 1) center = true;
for (int y = x + 1; y < 26; y++) len += min(cnt[x][y], cnt[y][x]) * 4;
}
return len + (center ? 2 : 0);
}JavaScript
var longestPalindrome = function(words) {
var cnt = [];
for (var i = 0; i < 26; i++) cnt.push(new Array(26).fill(0));
for (var w = 0; w < words.length; w++) cnt[words[w].charCodeAt(0) - 97][words[w].charCodeAt(1) - 97]++;
var len = 0, center = false;
for (var x = 0; x < 26; x++) {
len += Math.floor(cnt[x][x] / 2) * 4;
if (cnt[x][x] % 2 === 1) center = true;
for (var y = x + 1; y < 26; y++) len += Math.min(cnt[x][y], cnt[y][x]) * 4;
}
return len + (center ? 2 : 0);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.