Solution: Palindrome Pairs

Statement

You are given a 0-indexed array of unique strings called words.

A palindrome pair is defined as a pair of indexes (i, j) where both i and j are within the valid range of the list of words (that is, $0 \leq$ i, j $<$ words.length), and i is not equal to j. The key condition is that when the word at index i is concatenated with the word at index j (forming words[i] + words[j]), the resulting string must be a palindrome.

Your task is to return all valid palindrome pairs as a list of index pairs.

Additionally, your solution must have a time complexity of $O(\text{sum of}$ words.length$)$.

Constraints:

• $1 \leq$ words.length $\leq 1000$

• $0 \leq$ words[i].length $\leq 300$

• words[i] consists of lowercase English letters

• All strings in words unique

Solution

To solve this problem efficiently, we need to understand the different ways two words can be combined to form a palindrome. The most straightforward case is when one word is the reverse of the other—placing them in either order will produce a palindrome. However, there are more subtle cases as well. Suppose there is a word that starts with a substring that is a palindrome, and the other word is the reverse of the remaining suffix—their concatenation will form a palindrome. Similarly, if one word ends with a palindrome and the other word is the reverse of the remaining prefix, the pair can still form a valid palindrome when combined in the right order. These three cases form the core idea behind our solution and are illustrated below: