Palindrome Pairs — HashMap Split Enumeration (Hard)

Problem Statement#

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

Constraints:

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

Input:  ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
 
Explanation:
  abcd + dcba = abcddcba (palindrome)
  dcba + abcd = dcbaabcd (palindrome)
  s    + lls  = slls     (palindrome)
  lls  + sssll = llssssll (palindrome)

Why This Problem Matters#

Palindrome Pairs is a classic Google and Amazon hashmap interview problem that tests whether you can recognize when O(N^2) brute force is unacceptable and replace it with a clever hash table FAANG-style decomposition. Naively comparing every pair of words costs O(N^2 * K) where K is word length — for N = 5000 and K = 300, that is 7.5 billion operations. Production systems and onsite interviews demand the O(N * K^2) hashmap approach.

The pattern here — split each word at every index, look up the reverse of one half, and verify the other half is itself a palindrome — appears across many string problems: shortest palindrome, palindrome partitioning II, and even compiler tokenization tasks. Mastering it teaches you to convert "for each pair" thinking into "for each word, query the map" thinking, the heart of the hashmap interview pattern.

This problem also surfaces tricky edge cases (empty strings, self-pairs, duplicate matches) that interviewers love because they reveal whether candidates code defensively. Getting it right under pressure is a strong signal of senior-level data structure intuition.

The Core Insight#

If words[i] + words[j] is a palindrome, split it at the boundary between words[i] and words[j]. There are three structural cases:

1. Equal length: words[i] is the exact reverse of words[j]. Look up reverse(words[i]) in the map.
2. words[i] longer: words[i] = palindrome_prefix + reverse(words[j]). The leftover prefix of words[i] must itself be a palindrome.
3. words[j] longer: words[i] = reverse(words[j]_suffix) and the leftover suffix of words[j] must be a palindrome.

Build a hashmap {word: index}. For each word, try every split point (left, right). If left is a palindrome and reverse(right) exists in the map, that map entry can sit BEFORE the current word. If right is a palindrome and reverse(left) exists in the map, that entry can sit AFTER the current word. The empty string handles the equal-length case symmetrically.

Visual Dry Run#

Words: ["abcd", "dcba", "lls", "s", "sssll"]

Map: abcd to 0, dcba to 1, lls to 2, s to 3, sssll to 4

Final result: [[0,1], [1,0], [3,2], [2,4]].

Solution (Optimal)#

class Solution:
    def palindromePairs(self, words):
        def is_pal(s, i, j):
            while i < j:
                if s[i] != s[j]:
                    return False
                i += 1
                j -= 1
            return True
 
        index = {w: i for i, w in enumerate(words)}
        result = []
 
        for i, w in enumerate(words):
            n = len(w)
            for cut in range(n + 1):
                left = w[:cut]
                right = w[cut:]
 
                # Case A: left is palindrome -> need reverse(right) BEFORE w
                if is_pal(w, 0, cut - 1):
                    rev_right = right[::-1]
                    if rev_right in index and index[rev_right] != i:
                        result.append([index[rev_right], i])
 
                # Case B: right is palindrome -> need reverse(left) AFTER w
                # Skip cut == n to avoid duplicate of Case A when right is empty
                if cut != n and is_pal(w, cut, n - 1):
                    rev_left = left[::-1]
                    if rev_left in index and index[rev_left] != i:
                        result.append([i, index[rev_left]])
 
        return result

var palindromePairs = function(words) {
    const isPal = (s, i, j) => {
        while (i < j) {
            if (s[i] !== s[j]) return false;
            i++;
            j--;
        }
        return true;
    };
 
    const index = new Map();
    for (let i = 0; i < words.length; i++) index.set(words[i], i);
 
    const result = [];
 
    for (let i = 0; i < words.length; i++) {
        const w = words[i];
        const n = w.length;
        for (let cut = 0; cut <= n; cut++) {
            const left = w.slice(0, cut);
            const right = w.slice(cut);
 
            // Case A: left palindrome -> reverse(right) sits before w
            if (isPal(w, 0, cut - 1)) {
                const revRight = right.split('').reverse().join('');
                if (index.has(revRight) && index.get(revRight) !== i) {
                    result.push([index.get(revRight), i]);
                }
            }
 
            // Case B: right palindrome -> reverse(left) sits after w
            if (cut !== n && isPal(w, cut, n - 1)) {
                const revLeft = left.split('').reverse().join('');
                if (index.has(revLeft) && index.get(revLeft) !== i) {
                    result.push([i, index.get(revLeft)]);
                }
            }
        }
    }
 
    return result;
};

Time: O(N * K^2) — for each of N words we try K + 1 splits and each palindrome check is O(K). Space: O(N * K) for the hashmap of words plus the output.

Common Mistakes#

• Adding the same pair twice when one of the words is empty — handled by the cut != n guard in Case B.
• Forgetting the self-pair filter (index[x] != i), which produces invalid pairs like (3, 3).
• Reversing the wrong half — Case A reverses right, Case B reverses left.
• Mishandling cut == 0 or cut == n so the empty string is not treated as a palindrome.
• Producing duplicate ordered pairs because both Case A and Case B fire for the same split when one half is empty.

Interview Tips#

• Open by stating the brute force O(N^2 * K) and why it fails at N = 5000, K = 300.
• Walk through the three structural cases on the whiteboard before writing code — this signals you understand WHY the algorithm works, not just HOW.
• Mention the trie alternative (O(N * K^2) too, but uses less memory for short words) if the interviewer pushes for follow-ups.
• Always discuss the empty-string edge case proactively — many candidates miss it and lose points.

Follow-up Questions#

• How would you adapt this if words could repeat? Hint: store a list of indices per word.
• Could you use a trie instead of a hashmap? Hint: traverse the trie with the reversed prefix while tracking palindrome suffixes at each node.
• What if you only need to count palindrome pairs, not list them? Hint: same loop, increment a counter, but watch for double counting via cases A and B.
• How would you parallelize this for a billion-word corpus? Hint: shard by first-letter bucket and use Spark or MapReduce.
• Can you handle Unicode without breaking the reverse step? Hint: iterate over code points or grapheme clusters, not bytes.

Key Takeaways#

• Palindrome Pairs reduces from O(N^2 * K) to O(N * K^2) by precomputing a {word: index} hashmap and querying it for each split.
• The three structural cases (equal length, longer prefix, longer suffix) collapse into two when cut ranges over [0, n] inclusive.
• The empty-prefix split handles the equal-length / exact-reverse case for free.
• Always exclude self-pairs by comparing the looked-up index to the current word's index.
• The dual guard cut != n in Case B prevents double counting when a word is itself a palindrome.
• A trie-based solution achieves the same complexity with better memory locality on long words.
• This is a top-tier Google and Amazon onsite question that rewards crisp case analysis.