Longest Palindrome by Concatenating Two Letter Words

Longest Palindrome by Concatenating Two Letter Words

What is this problem about?

In this problem, you are given an array of 2-letter words (e.g., ["lc", "cl", "gg"]). You can select any number of these words and concatenate them in any order to form a palindrome. Your goal is to return the maximum length of the palindrome you can create. Every word you use can only be used once.

Why is this asked in interviews?

This is a highly popular medium-level question at companies like Google and Meta. It is a more constrained, tightly focused version of general string concatenation problems. Because every word is exactly 2 letters, it acts as a perfect playground for Hash Maps and counting. Interviewers love it because it looks like a recursion/backtracking problem, but is actually a pure $O(N)$ logic puzzle.

Algorithmic pattern used

This problem utilizes a Greedy approach via a Frequency Map / Hash Table. You iterate through the list of words and count their frequencies. For an asymmetric word like "ab", it can only be used if you also have a "ba". You take the minimum count of "ab" and "ba" and pair them up. For a symmetric word like "xx", you can pair them with each other (if you have two "xx"s). Finally, if you have any single symmetric word left over, you can place it perfectly in the center of the palindrome.

Example explanation

Let words = ["lc", "cl", "gg", "gg", "ab", "ll"].

1. "lc" and "cl": We have one of each. We pair them. Length += 4. (Palindrome is "lc...cl").
2. "ab": We have no "ba". Useless.
3. "gg": We have two. Since it's symmetric, we pair them with each other! Length += 4. (Palindrome is "lc" + "gg" + "gg" + "cl").
4. "ll": We have one. We can't pair it. However, because it is symmetric, we can place exactly one such word in the absolute center of our palindrome! Length += 2. Total max length = 4 + 4 + 2 = 10. (e.g., "lcggllggcl").

Common mistakes candidates make

A major pitfall is iterating through the array and deleting elements as you find matches, which requires messy nested loops. Another common error is how candidates handle the symmetric words (like "gg"). Candidates sometimes assume all "gg"s must go in the middle. Remember, you can put "gg" on the far left and the other "gg" on the far right. Only an unpaired, single symmetric word is relegated to the center.

Interview preparation tip

For the Longest Palindrome by Concatenating Two Letter Words coding problem, building a 2D array of size 26x26 is actually much faster than using a Hash Map. Since the strings are strictly 2 lowercase letters, char1 - 'a' is the row and char2 - 'a' is the column. This gives you ultra-fast $O(1)$ updates and reads, impressing the interviewer with your spatial optimization skills.