Palindrome Pairs

You are given a list of distinct strings words made of lowercase English letters (a word may be the empty string).

A palindrome pair is an ordered pair of indices [i, j] with i != j such that gluing the two words together, words[i] + words[j], reads the same forwards and backwards. Note that [i, j] and [j, i] are different pairs and each one counts only if its own concatenation is a palindrome.

Return every palindrome pair. The pairs may be listed in any order.

Example 1

Example 2

Example 3

Constraints

• 1 <= words.length <= 5000
• 0 <= words[i].length <= 300
• words[i] consists of lowercase English letters.
• All strings in words are distinct.

Pattern Path · Hashing & Counting · problem 13 of 169

Start simple

Concatenate every ordered pair of words and test it: O(n²·L) time, where L is the maximum word length.

The key idea

Look at a palindrome A + B where B is no longer than A. Its last |B| characters are B, so its first |B| characters must be B reversed. Whatever is left in the middle of A must mirror itself, i.e. be a palindrome. So a long word determines its short partners completely: split it, check that one piece is a palindrome, and the partner must be the other piece reversed.

Store each word's index in a hash map. For every word and every cut word = left + right:

• If right is a palindrome and reverse(left) is a different word j, then word + words[j] works: record [i, j].
• If left is a palindrome and reverse(right) is a different word j, then words[j] + word works: record [j, i].

When the cut is at position 0, the second rule looks up the full reverse of the word, which the first rule already finds from the partner's side at its last cut. Skipping that one cut prevents duplicates. Each word has L + 1 cuts and each cut does O(L) work, giving O(n·L²) in total.

Complexity

• Time: O(n·L²), where L is the maximum word length
• Space: O(n·L)

Python

class Solution:
    def palindromePairs(self, words):
        index = {word: i for i, word in enumerate(words)}
        result = []
        for i, word in enumerate(words):
            for cut in range(len(word) + 1):
                left, right = word[:cut], word[cut:]
                # word + partner is a palindrome when `right` is a palindrome
                # and the partner is `left` reversed.
                if right == right[::-1]:
                    j = index.get(left[::-1])
                    if j is not None and j != i:
                        result.append([i, j])
                # partner + word is a palindrome when `left` is a palindrome
                # and the partner is `right` reversed. Skipping cut == 0 avoids
                # finding the "partner is the full reverse" case twice.
                if cut > 0 and left == left[::-1]:
                    j = index.get(right[::-1])
                    if j is not None and j != i:
                        result.append([j, i])
        return result

JavaScript

var palindromePairs = function(words) {
  const reverse = (s) => s.split('').reverse().join('');
  const isPalindrome = (s) => {
    for (let lo = 0, hi = s.length - 1; lo < hi; lo++, hi--) {
      if (s[lo] !== s[hi]) return false;
    }
    return true;
  };

  const index = new Map();
  words.forEach((word, i) => index.set(word, i));

  const result = [];
  words.forEach((word, i) => {
    for (let cut = 0; cut <= word.length; cut++) {
      const left = word.slice(0, cut);
      const right = word.slice(cut);
      // word + partner: `right` is a palindrome, partner is `left` reversed.
      if (isPalindrome(right)) {
        const j = index.get(reverse(left));
        if (j !== undefined && j !== i) result.push([i, j]);
      }
      // partner + word: `left` is a palindrome, partner is `right` reversed.
      // Skipping cut === 0 avoids finding the full-reverse case twice.
      if (cut > 0 && isPalindrome(left)) {
        const j = index.get(reverse(right));
        if (j !== undefined && j !== i) result.push([j, i]);
      }
    }
  });
  return result;
};

What the interviewer is checking

The interviewer wants to see you turn a pairwise search into a lookup by reasoning about what a partner must look like, and then handle the empty string and duplicate pairs carefully.

Mistakes to avoid

• Pairing a palindromic word with itself; the two indices must differ.
• Reporting the same pair twice when the partner is the exact reverse of the word.
• Forgetting the empty string, which pairs with every palindromic word in both orders.
• Only checking partners of equal length and missing pairs like "lid" + "sdil".

Follow-ups to expect

• How would a trie of reversed words speed this up? (Walk the trie, check remaining suffix.)
• What if you only need to count pairs? (Same lookups, add instead of collect.)
• What if words can repeat? (Map word to list of indices.)

In real software

Splitting a string and looking up the complementary piece in a hash table is how spell checkers and DNA tools find words or sequences that join to form a target pattern.

Practice next