Longest Palindrome by Concatenating Two Letter Words
Problem
You are given an array of two-letter strings. Return the length of the longest palindrome you can build by concatenating some of these strings.
words = ["lc", "cl", "gg"]6def longest_palindrome(words):
from collections import Counter
cnt = Counter(words)
ans, center = 0, False
for w, c in cnt.items():
r = w[::-1]
if w == r:
ans += (c // 2) * 4
if c % 2: center = True
elif w < r:
ans += min(c, cnt.get(r, 0)) * 4
return ans + (2 if center else 0)function longestPalindrome(words) {
const cnt = new Map();
for (const w of words) cnt.set(w, (cnt.get(w) || 0) + 1);
let ans = 0, center = false;
for (const [w, c] of cnt) {
const r = w[1] + w[0];
if (w === r) {
ans += Math.floor(c / 2) * 4;
if (c % 2) center = true;
} else if (w < r) {
ans += Math.min(c, cnt.get(r) || 0) * 4;
}
}
return ans + (center ? 2 : 0);
}class Solution {
public int longestPalindrome(String[] words) {
Map<String, Integer> cnt = new HashMap<>();
for (String w : words) cnt.merge(w, 1, Integer::sum);
int ans = 0; boolean center = false;
for (Map.Entry<String, Integer> e : cnt.entrySet()) {
String w = e.getKey(); int c = e.getValue();
String r = "" + w.charAt(1) + w.charAt(0);
if (w.equals(r)) {
ans += (c / 2) * 4;
if (c % 2 == 1) center = true;
} else if (w.compareTo(r) < 0) {
ans += Math.min(c, cnt.getOrDefault(r, 0)) * 4;
}
}
return ans + (center ? 2 : 0);
}
}int longestPalindrome(vector<string>& words) {
unordered_map<string, int> cnt;
for (auto& w : words) cnt[w]++;
int ans = 0; bool center = false;
for (auto& [w, c] : cnt) {
string r = string(1, w[1]) + w[0];
if (w == r) {
ans += (c / 2) * 4;
if (c % 2) center = true;
} else if (w < r) {
ans += min(c, cnt.count(r) ? cnt[r] : 0) * 4;
}
}
return ans + (center ? 2 : 0);
}Explanation
A palindrome reads the same both ways, so if a two-letter word sits on the left side, its reverse must sit on the matching spot on the right. The whole trick is pairing each word with its mirror, plus an optional special word in the dead center.
We count every word with a counter cnt. For a word w whose reverse is r: if w != r (like "lc" and "cl"), we can form min(cnt[w], cnt[r]) mirrored pairs, and each pair contributes 4 letters to the palindrome. We only handle this when w < r so each pair is counted once.
If a word is its own reverse (like "gg"), copies pair up among themselves: (cnt // 2) * 4 letters. If there's an odd leftover of such a self-palindrome, one copy can sit exactly in the middle, adding 2 more letters — but only one center is allowed.
Example: words = ["lc","cl","gg"]. The lc/cl pair gives 4 letters, and the single "gg" goes in the center for 2 letters, totaling 6 (for example "lcggcl").
At the end we add 2 if any center word was available. Everything is a single pass over the distinct words.