Palindrome Pairs - Video Solutions

Problem Overview: You are given a list of unique words. The task is to return all pairs of indices (i, j) such that concatenating words[i] + words[j] forms a palindrome. The challenge is efficiently checking many string combinations without recomputing palindrome checks repeatedly.

Approach 1: Brute Force Check with Reversed Strings (O(n² * k) time, O(1) extra space)

The straightforward solution checks every ordered pair of words. For each pair (i, j), concatenate the two strings and verify if the result is a palindrome using two pointers from both ends. With n words and average length k, each concatenation check costs O(k), giving overall complexity O(n^2 * k). A small improvement is to precompute reversed versions of each string so you can quickly compare segments instead of building full concatenations. This approach relies mainly on simple array iteration and string comparison. It works well for small input sizes but quickly becomes slow when the number of words grows.

Approach 2: Using Trie Data Structure (O(n * k^2) time, O(n * k) space)

A more scalable approach builds a Trie containing reversed words. While inserting each reversed word, store indices of words whose remaining prefix forms a palindrome. This extra bookkeeping allows efficient matching later. When processing a word, iterate through its characters and walk the Trie simultaneously. If you encounter a Trie node that marks the end of another word and the remaining substring of the current word is a palindrome, you found a valid pair.

After reaching the end of the word in the Trie, any stored indices in that node represent words whose leftover suffix is already palindromic. Those indices also form valid pairs. This technique avoids comparing every pair directly and instead performs structured lookups. The Trie organizes reversed words by prefix, which makes matching efficient. The method combines concepts from Trie, hash table-style indexing, and repeated palindrome checks on substrings.

The key insight is splitting each word at every possible boundary. If the prefix is a palindrome, the reversed suffix may match another word. If the suffix is a palindrome, the reversed prefix may match. The Trie helps locate those matches quickly without scanning all words.

Recommended for interviews: Start with the brute force approach to show understanding of the problem and correctness of palindrome checks. Interviewers typically expect a more optimized design afterward. The Trie-based solution demonstrates stronger algorithmic thinking and knowledge of advanced string indexing techniques, which is why it is the preferred discussion in most senior-level interviews.