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

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:

Regarding the implementation, the three cases above can be handled as follows:

1. Case 1: Check if the reverse of the word exists in the list. If it does, then combining the word with its reverse forms a palindrome.

2. Case 2: For each suffix of the word, check if it is a palindrome. If it is, reverse the remaining prefix and check if that exists in the list. If found, appending that reverse prefix before the word will form a palindrome.

3. Case 3: For each prefix of the word, check if it is a palindrome. If it is, reverse the ...