AlgoMaster Logo

Palindrome Pairs

hardFrequencyUpdated September 21, 2026

Understanding the Problem

We have a list of unique strings, and we need to find every ordered pair (i, j) where concatenating words[i] with words[j] produces a palindrome. The pairs are ordered, so (i, j) and (j, i) are different and both can be valid. For instance, "abcd" + "dcba" and "dcba" + "abcd" are both palindromes.

When does concatenating two strings create a palindrome? If words[i] is the exact reverse of words[j], the concatenation is a palindrome. That is not the only case. Take "s" and "lls": the concatenation "slls" is a palindrome even though neither word is the full reverse of the other. Here "s" matches the trailing "s" of "lls", and the leftover part "ll" is itself a palindrome sitting in the middle.

That observation generalizes into a decomposition. Split a word into a prefix and a suffix. If the prefix is a palindrome and the reverse of the suffix exists in the list, that reversed suffix can sit before the word to complete a palindrome. If the suffix is a palindrome and the reverse of the prefix exists in the list, that reversed prefix can sit after the word. These two cases cover every palindrome pair.

Key Constraints:

  • 1 <= words.length <= 5000 → Checking all n^2 ordered pairs is 25 million pairs, and each pair costs another O(k) to verify, so the brute force is O(n^2 * k). With words up to 300 characters that is too slow, which pushes us toward decomposing each word and looking partners up directly.
  • 0 <= words[i].length <= 300 → Words can be empty. An empty string paired with any palindromic word forms a valid pair in both directions, so the empty string is an edge case the decomposition has to handle.
  • words[i] consists of lowercase English letters → The 26-letter alphabet keeps a trie node small (a fixed 26-way branch), which makes the trie approach practical.

Approach 1: Brute Force

Intuition

Translate the problem statement directly: try every ordered pair (i, j) where i != j, concatenate the two words, and check whether the result is a palindrome.

Checking whether a string is a palindrome takes O(k) time where k is the length of the concatenated string, and there are n^2 pairs to check. This is correct but quadratic in the number of words.

Algorithm

  1. Initialize an empty result list.
  2. For each pair (i, j) where i != j, concatenate words[i] + words[j].
  3. Check if the concatenated string is a palindrome by comparing characters from both ends.
  4. If it is a palindrome, add [i, j] to the result.
  5. Return the result list.

Visualization and Code

Loading animation...

The brute force ignores the structure of the strings, comparing every word against every other word. The next approach uses that structure: it decomposes each word and looks up potential partners in a hash map.

Approach 2: Hash Map with Palindrome Decomposition

Intuition

Split words[i] at every position into a prefix and a suffix. If the prefix is a palindrome, then any word equal to the reverse of the suffix can sit before words[i] to form a palindrome. If the suffix is a palindrome, then any word equal to the reverse of the prefix can sit after words[i]. Storing every word with its index in a hash map turns each of these lookups into O(1), so the only cost per word is forming the prefixes and suffixes and reversing them.

Algorithm

  1. Build a hash map from each word to its index.
  2. For each word at index i, try every split position j from 0 to len(word) (inclusive, so both the empty prefix and the empty suffix are covered):
    • Let prefix = word[0..j] and suffix = word[j..end].
    • Check 1: If prefix is a palindrome and the reverse of suffix exists in the map at some index k != i, then words[k] placed before the word completes a palindrome, so add [k, i].
    • Check 2: If suffix is non-empty and a palindrome, and the reverse of prefix exists at some index k != i, then words[k] placed after the word completes a palindrome, so add [i, k].
  3. Return all collected pairs.

The suffix non-empty guard in Check 2 prevents counting the same pair twice. When j equals len(word), the suffix is empty and the prefix is the whole word. That case is already handled by Check 1 at j = 0, where the prefix is empty (a palindrome) and the suffix is the whole word, so skipping the empty-suffix branch removes the duplicate.

Visualization and Code

Loading animation...

The hash map approach avoids checking all pairs, but it still builds and reverses O(k) substrings per word. The next approach stores the words in a trie of their reversed forms and walks it character by character, matching partners during the traversal instead of constructing substrings.

Approach 3: Trie of Reversed Words

Intuition

Build a trie from the reversed words, then for each word w walk the trie character by character following w. Two situations produce a pair, both finding a partner p such that w + p is a palindrome:

  • A full reversed word ends at the current trie node while characters of w remain. That stored word equals the reverse of a prefix of w, so it cancels that prefix. The remaining suffix of w must itself be a palindrome for the concatenation to work, so we check that before recording the pair.
  • We consume all of w and land on some node. Any reversed word stored at or below that node has w as a prefix of its reverse, so it covers all of w and extends further. The extra characters it carries must form a palindrome. We pre-compute, at each node during insertion, the list of word indices whose remaining (deeper) portion is a palindrome, so the lookup at the end is a single list read.

Algorithm

  1. Insert each word into the trie character by character from its last character to its first (so the stored path is the reversed word). Before consuming character i (counting from the end), the still-unconsumed front of the word is word[0..i]. If that front is a palindrome, record this word's index in a palindromeBelow list at the current node. At the final node, store the word's index as wordIdx and also append it to palindromeBelow (the empty remainder counts as a palindrome).
  2. For each word, traverse the trie following its characters left to right. At each node, if a complete reversed word ends there (wordIdx set and not equal to the current word's index) and the unread tail of the current word is a palindrome, record [idx, wordIdx]. After consuming the whole word, every index in the current node's palindromeBelow list (except the word itself) forms a pair [idx, k].

Visualization and Code

Loading animation...