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 1000$
• words[i].length $= 2$
• Each word can be used at most once.
• words should only consist of lowercase English letters.

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 ...