Checking every two pairs will exceed the time limit. It will be O(n^2 * k). We need a faster way.

If we hash every string in the array, how can we check if two pairs form a palindrome after the concatenation?

We can check every string in words and consider it as words[j] (i.e., the suffix of the target palindrome). We can check if there is a hash of string that can be the prefix to make it a palindrome.