Skip to content

Practice Longest Palindrome by Concatenating Two Letter Words

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Medium#2131
LeetCode Problem

Longest Palindrome by Concatenating Two Letter Words

Problem Statement

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.

Source: Longest Palindrome by Concatenating Two Letter Words on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
words = ["lc","cl","gg"]
Output
6
Explanation

Place "lc" on the left, its reverse "cl" on the right, and the self-reversing word "gg" in the middle. This forms "lcggcl", which reads identically in both directions and has length 6. All three available words are used, so no longer result is possible. Each non-symmetric two-letter word needs its reversed partner on the opposite side; a word such as "gg" can instead occupy the single central position.

# Example 2

Input
words = ["ab","ty","yt","lc","cl","ab"]
Output
8
Explanation

The reversible pairs are "ty" with "yt" and "lc" with "cl". Arranging them as "ty" + "lc" + "cl" + "yt" produces the palindrome "tylcclyt", of length 8. Neither copy of "ab" can be used: there is no "ba" for its mirror position, and "ab" cannot be a palindrome center. Thus only four of the six words are usable. Two identical non-symmetric words do not substitute for a word and its reverse.

# Example 3

Input
words = ["cc","ll","xx"]
Output
2
Explanation

Each available word is a palindrome by itself, so choosing "cc", "ll", or "xx" gives length 2. A longer palindrome would need matching two-letter words on opposite sides, but every word occurs only once. There is also only one central word position, so the three unmatched self-reversing words cannot all be placed in the center. The maximum length is therefore 2, not the total length of the individually palindromic words.

Constraints

1 <= words.length <= 10^5
words[i].length == 2
words[i] consists of lowercase English letters.

How to solve Longest Palindrome by Concatenating Two Letter Words

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

A word and its reversal placed symmetrically contribute four characters, two copies of a doubled word such as gg pair with each other the same way, and at most one leftover doubled word can sit in the center; counting words turns all three contributions into arithmetic.

Why brute force is not enough

Trying subsets and orderings of up to 10^5 words to find the longest palindrome is factorial time; even a backtracking search over which word comes next is infeasible beyond a few dozen words.

Approach

  1. Count occurrences of each distinct two-letter word in a hash map or a 26 by 26 table.
  2. For each word whose letters differ, pair it with its reversal: the number of usable pairs is the minimum of the two counts and each pair adds 4; process each unordered pair once, for example only when the first letter is smaller than the second.
  3. For each doubled word, floor(count / 2) pairs add 4 each; if the count is odd, remember that a center candidate exists.
  4. Add 2 to the total if any center candidate was found, since only one word can occupy the center.
  5. Return the total, which is 0 when no pairs and no doubled words exist.

Walkthrough of Example 2

words = ["ab","ty","yt","lc","cl","ab"] → 8

  1. Counts: ab 2, ty 1, yt 1, lc 1, cl 1.
  2. ty with yt gives min(1, 1) = 1 pair, adding 4; lc with cl gives 1 pair, adding 4; ab has no ba, so it contributes nothing.
  3. There are no doubled words, so no center is added.
  4. Total 8, realized as ty lc cl yt.

Time and space

Time O(n) · Space O(1). n is the number of words; counting and the pairing pass each touch every distinct word once, and the table has at most 676 entries regardless of n.

Interview pitfalls

  • Counting the ab and ba pairing from both sides, doubling its contribution.
  • Adding 2 for every doubled word with an odd count instead of once in total.
  • Pairing a doubled word with itself as if it were a reversal pair and skipping the floor division by 2.
  • Treating two copies of ab as a matching pair; they are not reversals of each other.
  • Returning 0 when there are doubled words but no reversal pairs; a single gg is already a palindrome of length 2.

Follow-up questions interviewers ask

  • How would you construct and return one longest palindrome rather than just its length?
  • What changes if words have length 3, where the middle letters must match and reversal remains the pairing rule?
  • If words stream in and the answer is queried repeatedly, how do you update the total in O(1) per word?

Further reading on the technique: Hash table

Related LeetCode Problems

Practice more problems similar to Longest Palindrome by Concatenating Two Letter Words.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.