Palindrome Pairs — Reverse Trie + Palindrome Tail Check

Problem Statement#

LeetCode 336 — Palindrome Pairs | Difficulty: Hard

Given a list of unique words, return all the pairs of distinct indices (i, j) in the given list such that the concatenation of the two words words[i] + words[j] is a palindrome.

You must write an algorithm with O((sum of word lengths)^2) time complexity at worst, but better solutions exist.

Constraints:

• 1 <= words.length <= 5000
• 0 <= words[i].length <= 300
• words[i] consists of lowercase English letters.

Examples:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: Palindromes formed are
  ["abcddcba","dcbaabcd","slls","llssssll"]

Input: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: "battab" and "tabbat" are palindromes.

Input: words = ["a",""]
Output: [[0,1],[1,0]]

Why This Problem Matters#

Palindrome Pairs is the classic "trie + palindromes" hard problem. Google, Amazon, and Microsoft use it as a litmus test because the elegant solution requires three insights stacked on top of each other — reverse storage, palindrome-suffix tagging, and three case decomposition. Solving it cold demonstrates mature data-structure thinking.

The naive O(N^2 times K) approach (concatenate every pair, check palindrome) handles small inputs but TLEs at 5000 words of length 300. The trie solution drops to O(N times K^2) — typically 100x faster — and forms the basis of efficient string-matching engines.

The Core Insight#

For a pair (i, j) such that words[i] + words[j] is a palindrome, exactly one of three cases holds. Let A = words[i], B = words[j], where len(A) >= len(B) (without loss of generality, similar cases for the reverse):

1. Equal length — A is the reverse of B (A + B reversed = A + reverse(A) = palindrome).
2. A is longer — A = X + Y where Y is a palindrome and B = reverse(X). Then A + B = X + Y + reverse(X), which is a palindrome.
3. B is longer — B = reverse(Y) + X where Y is a palindrome and A = reverse(X). Then A + B = reverse(X) + reverse(Y) + X = palindrome.

Strategy: insert every word reversed into a trie. Tag each node with the indices of the words whose remaining suffix (after this point) is a palindrome. For each query word, walk the trie with the original characters, splitting into the three cases based on where the walk ends.

Visual Dry Run#

Words: ["abcd", "dcba", "lls", "s", "sssll"]. Insert each reversed:

"abcd" reversed: "dcba"  → root → d → c → b → a
"dcba" reversed: "abcd"  → root → a → b → c → d
"lls"  reversed: "sll"   → root → s → l → l
"s"    reversed: "s"     → root → s
"sssll"reversed: "llsss" → root → l → l → s → s → s

At each node we also tag indices of words for which the remaining reversed suffix is a palindrome. Querying "lls":

Walk trie: l → ?  No 'l' child of root in this trie.
Wait: actually we insert REVERSED, so root has children {d, a, s, l}.
Walk 'l': root has 'l'? yes (from "llsss")
Walk 'l': child 'l' yes
Walk 's': child 's' yes
End of query word — at this node we look up "indices for which the remaining tail is palindromic".

If at the end-of-walk node we have a stored index j, and words[j][len(query):] is itself a palindrome, then (i, j) is a valid pair (case 3). Symmetrically for the other cases.

Solution (Optimal) — Reverse Trie + Palindrome Tags#

Python#

class TrieNode:
    __slots__ = ("children", "word_idx", "palindrome_below")
    def __init__(self):
        self.children = {}
        self.word_idx = -1                # index if word ends here
        self.palindrome_below: list[int] = []  # words whose remaining tail is palindrome
 
class Solution:
    def palindromePairs(self, words: list[str]) -> list[list[int]]:
        def is_palindrome(s: str, lo: int, hi: int) -> bool:
            while lo < hi:
                if s[lo] != s[hi]:
                    return False
                lo += 1; hi -= 1
            return True
 
        root = TrieNode()
 
        # Insert reversed words; tag palindrome_below at each node
        for idx, w in enumerate(words):
            node = root
            n = len(w)
            for k in range(n - 1, -1, -1):
                # If the prefix w[0..k] is a palindrome, this index "fits" at the current node
                if is_palindrome(w, 0, k):
                    node.palindrome_below.append(idx)
                ch = w[k]
                node = node.children.setdefault(ch, TrieNode())
            node.word_idx = idx
            node.palindrome_below.append(idx)  # empty tail is palindromic
 
        result: list[list[int]] = []
 
        # For each word, walk the trie with original chars
        for idx, w in enumerate(words):
            node = root
            n = len(w)
            for k, ch in enumerate(w):
                # Case 2: trie has a word that ends at current node and the rest of w is palindrome
                if node.word_idx >= 0 and node.word_idx != idx and is_palindrome(w, k, n - 1):
                    result.append([idx, node.word_idx])
                if ch not in node.children:
                    break
                node = node.children[ch]
            else:
                # Walked whole word — case 1 and case 3
                for j in node.palindrome_below:
                    if j != idx:
                        result.append([idx, j])
        return result

JavaScript#

var palindromePairs = function (words) {
  const isPal = (s, lo, hi) => {
    while (lo < hi) {
      if (s[lo] !== s[hi]) return false;
      lo++; hi--;
    }
    return true;
  };
 
  const root = { children: {}, wordIdx: -1, palBelow: [] };
 
  for (let idx = 0; idx < words.length; idx++) {
    const w = words[idx];
    let node = root;
    for (let k = w.length - 1; k >= 0; k--) {
      if (isPal(w, 0, k)) node.palBelow.push(idx);
      const ch = w[k];
      if (!node.children[ch]) node.children[ch] = { children: {}, wordIdx: -1, palBelow: [] };
      node = node.children[ch];
    }
    node.wordIdx = idx;
    node.palBelow.push(idx);
  }
 
  const result = [];
  for (let idx = 0; idx < words.length; idx++) {
    const w = words[idx];
    let node = root, broke = false;
    for (let k = 0; k < w.length; k++) {
      if (node.wordIdx >= 0 && node.wordIdx !== idx && isPal(w, k, w.length - 1)) {
        result.push([idx, node.wordIdx]);
      }
      const ch = w[k];
      if (!node.children[ch]) { broke = true; break; }
      node = node.children[ch];
    }
    if (!broke) {
      for (const j of node.palBelow) {
        if (j !== idx) result.push([idx, j]);
      }
    }
  }
  return result;
};

Complexity#

• Time: O(N times K^2) where N = number of words, K = max word length. Each insert is O(K^2) due to palindrome checks; each query is O(K^2).
• Space: O(N times K) for the trie plus O(N times K) for palindrome_below lists in the worst case.

Common Mistakes#

1. Forgetting the empty string — "" pairs with every palindrome word in the list. Handle by tagging the root if "" is present.
2. Not excluding self-pairs — (i, i) is invalid even if word + word is a palindrome.
3. Confusing the two directions — pairs are ordered: (i, j) and (j, i) are both valid if both concatenations are palindromes.
4. Storing indices only at terminals — case 3 needs indices at every prefix node where the remaining tail is palindromic, not just at the end.
5. Building the trie without reversing — defeats the purpose; you must reverse at insert so query walks naturally.
6. Using brute force only when N is small — borderline acceptable but not what hard problems test; the trie pattern is the expected answer.

Interview Tips#

• Walk through the three cases on a whiteboard before coding; the case decomposition is the hardest sell to interviewers.
• Insert reversed words to keep the query walk simple — explain why this maps query case 3 to "walked entire query, find palindrome below."
• Use an explicit helper isPalindrome(s, lo, hi) to keep palindrome checks inline cost obvious.
• Mention the alternative hash-map approach (split each word, look up reversed prefixes) — same complexity but more cases to manage.
• Be ready to discuss handling duplicates if the constraint were relaxed.

Follow-up Questions#

• What if word lengths can vary wildly? Build per-length buckets to keep palindrome checks bounded.
• Streaming inserts of new words? Update the trie incrementally; queries against existing words must be recomputed.
• Largest palindrome of length 3+ formed by concatenation? Filter pairs where the resulting length exceeds 2.
• Allow same word twice? Drop the j != idx guard — but then the empty string self-pairs.
• Manacher's algorithm here? Manacher gives O(K) palindrome checks for each prefix/suffix, dropping the K^2 factor; rarely required in interviews.

Key Takeaways#

• Three-case palindrome decomposition: equal length, A longer, B longer.
• Insert reversed words into the trie so query walks line up with concatenation.
• Tag every node along the insertion path where the remaining reversed tail is a palindrome — this enables case 3 in O(1) at the terminal.
• Always exclude i == j and consider the empty string as a special case.
• Complexity drops from O(N^2 K) to O(N K^2) — usually 100x speedup.
• This is the gold-standard hard trie problem; mastering it sets the bar for any FAANG hard string question.