Solution: Longest Palindrome by Concatenating Two-Letter Words

Statement

Suppose you are given an array of strings, words, and each element in the array has a length of two. You need to return the length of the longest palindrome that can be made by concatenating some elements from words. If no palindrome can be made, return 0.

A palindrome is a sequence of characters that reads the same forward and backward.

Constraints:

• $1 \leq$ words.length $\leq 10^6$
• words[i].length $= 2$
• Each word can be used at most once.

Solution

The solution to the problem involves concatenating strings to form a palindrome. We need to track which strings to combine in order to produce the longest palindrome. For example, the strings “ab” and “ba” can be concatenated to form the palindrome “abba”. Similarly, the strings “xy” and “yx” can be concatenated to form the palindrome “xyyx”. If we insert this palindrome in the middle of the first palindrome, we get “abxyyxba”, which is also a palindrome.

Let’s break the problem into two cases.

Case 1: A word is not a palindrome

Consider that a word is not a palindrome. For example, “ab” is not a palindrome. To include it in a palindromic sequence, we must pair it with its reverse, “ba”. Together, they will be part of the possible palindrome.

Note that when a word such as “ab” appears multiple times in an input array, the maximum number of times it can be used in a palindrome is the minimum of its occurrences and the occurrences of its reverse. For example, if “ab” appears 10 times, and “ba” appears seven times, we can only use a maximum of seven occurrences of both words in a palindrome.

To understand this better, let’s look at the illustration below: