#336 Palindrome Pairs

frequently reported atAirbnb Google Amazon

the problem

In plain words

You get an array of distinct words made of lowercase letters (a word may be empty). Return every pair of indices [i, j] with i ≠ j such that words[i] followed by words[j] reads the same forwards and backwards. The pairs can be in any order.

in words = ["abcd","dcba","lls","s","sssll"]

out [[0,1],[1,0],[3,2],[2,4]]

"abcddcba", "dcbaabcd", "slls", "llssssll".

in words = ["bat","tab","cat"]

out [[0,1],[1,0]]

in words = ["a",""]

out [[0,1],[1,0]]

The empty word pairs with every palindrome, on both sides.

1 ≤ words.length ≤ 5000
0 ≤ words[i].length ≤ 300
Lowercase English letters; all words are distinct

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTrie (prefix tree)Hash lookup (seen before?)

If words[i] + words[j] is a palindrome, the beginning of words[i] is words[j] read backwards, and whatever is left over in the middle reads the same both ways. So store every word reversed — then reading words[i] forwards down a trie of reversed words checks it against all j at once.

solutions

From brute force to optimal

Concatenate every words[i] + words[j] (i ≠ j) and check it with two pointers.

For every i and every j ≠ i: s = words[i] + words[j].
Two pointers from both ends; add [i, j] if all characters match.

timeO(n²·k)

n² ordered pairs, each built and checked in up to 2k characters — 25 million pairs for n = 5000.

spaceO(k)

One concatenated string at a time (output excluded).

javajava.util.*

1class Solution {2    public List<List<Integer>> palindromePairs(String[] words) {3        List<List<Integer>> pairs = new ArrayList<>();4        for (int i = 0; i < words.length; i++)5            for (int j = 0; j < words.length; j++)6                if (i != j && isPalindrome(words[i] + words[j])) pairs.add(List.of(i, j));7        return pairs;8    }9 10    private boolean isPalindrome(String s) {11        for (int lo = 0, hi = s.length() - 1; lo < hi; lo++, hi--)12            if (s.charAt(lo) != s.charAt(hi)) return false;13        return true;14    }15}

Cut words[i] into left + right at every position. If left is some word reversed and right is a palindrome, words[i] + that word works (and the mirror case for other + words[i]).

Map every reversed word to its index.
For each word and each cut 0..k: left = w[0..cut), right = w[cut..].
map has left and right is a palindrome → pair [i, map(left)].
cut > 0, map has right and left is a palindrome → pair [map(right), i] (cut > 0 avoids counting the whole word twice).

timeO(n·k²)

n words × (k + 1) cuts × an O(k) substring, hash and palindrome check.

spaceO(n·k)

The map of reversed words.

javajava.util.*

1class Solution {2    public List<List<Integer>> palindromePairs(String[] words) {3        Map<String, Integer> indexOfReversed = new HashMap<>();   // reversed word → its index4        for (int i = 0; i < words.length; i++) indexOfReversed.put(new StringBuilder(words[i]).reverse().toString(), i);5        List<List<Integer>> pairs = new ArrayList<>();6        for (int i = 0; i < words.length; i++) {7            String w = words[i];8            for (int cut = 0; cut <= w.length(); cut++) {9                String left = w.substring(0, cut), right = w.substring(cut);10                // w + other: other must be reverse(left), and the right part must read the same both ways11                Integer j = indexOfReversed.get(left);12                if (j != null && j != i && isPalindrome(right)) pairs.add(List.of(i, j));13                // other + w: other must be reverse(right), and the left part must be a palindrome14                // (cut > 0 so the whole-word match isn't counted twice)15                Integer k = indexOfReversed.get(right);16                if (cut > 0 && k != null && k != i && isPalindrome(left)) pairs.add(List.of(k, i));17            }18        }19        return pairs;20    }21 22    private boolean isPalindrome(String s) {23        for (int lo = 0, hi = s.length() - 1; lo < hi; lo++, hi--)24            if (s.charAt(lo) != s.charAt(hi)) return false;25        return true;26    }27}

Insert each word back to front; at every node remember which words have a palindrome left in their unread part. Walk each word forwards and collect matches.

Insert words[j] reversed. Before each step, if the part not yet inserted (a prefix of words[j]) is a palindrome, add j to the node's list; at the end, add j to the last node's list and mark the word ending there.
Walk words[i] forwards. At each node where a reversed word j ends, if the rest of words[i] is a palindrome → [i, j].
If words[i] is used up at a node, pair it with every j in that node's list (j ≠ i).

timeO(n·k²)

Each word is inserted and walked once (k steps each), but every step may run an O(k) palindrome check. No substrings or hashing, and walks stop where no reversed word continues.

spaceO(n·k)

Up to one trie node per letter, plus index lists (each word appears in at most k + 1 of them).

javajava.util.*

1class Solution {2    private static class Node {3        Node[] children = new Node[26];4        int wordEndsHere = -1;                              // index of the word whose reversal ends here5        List<Integer> restIsPalindrome = new ArrayList<>(); // words passing here whose unread part is a palindrome6    }7 8    public List<List<Integer>> palindromePairs(String[] words) {9        Node root = new Node();10        for (int j = 0; j < words.length; j++) addReversed(root, words[j], j);11        List<List<Integer>> pairs = new ArrayList<>();12        for (int i = 0; i < words.length; i++) collect(root, words, i, pairs);13        return pairs;14    }15 16    /** Inserts words[j] back to front. Before each step, notes j if the part not yet inserted is a palindrome. */17    private void addReversed(Node root, String word, int j) {18        Node cur = root;19        for (int k = word.length() - 1; k >= 0; k--) {20            if (isPalindrome(word, 0, k)) cur.restIsPalindrome.add(j);   // word[0..k] is still unread21            int c = word.charAt(k) - 'a';22            if (cur.children[c] == null) cur.children[c] = new Node();23            cur = cur.children[c];24        }25        cur.restIsPalindrome.add(j);                        // nothing left: the empty rest is a palindrome26        cur.wordEndsHere = j;27    }28 29    /** Reads words[i] forwards down the trie of reversed words: every match is a pair (i, j). */30    private void collect(Node root, String[] words, int i, List<List<Integer>> pairs) {31        String w = words[i];32        Node cur = root;33        for (int k = 0; k < w.length(); k++) {34            // case 1: a whole reversed word j ended, and the rest of words[i] is a palindrome35            if (cur.wordEndsHere >= 0 && cur.wordEndsHere != i && isPalindrome(w, k, w.length() - 1)) {36                pairs.add(List.of(i, cur.wordEndsHere));37            }38            cur = cur.children[w.charAt(k) - 'a'];39            if (cur == null) return;                        // no reversed word continues this way40        }41        // case 2: words[i] is used up; every word j whose unread beginning is a palindrome completes it42        for (int j : cur.restIsPalindrome) {43            if (j != i) pairs.add(List.of(i, j));44        }45    }46 47    private boolean isPalindrome(String s, int lo, int hi) {48        while (lo < hi) if (s.charAt(lo++) != s.charAt(hi--)) return false;49        return true;50    }51}

in the room

How to say it in the interview

talk track

Brute force first: n² pairs, each checked with two pointers — say the cost out loud.
Then the condition: words[i] = A + B with A equal to words[j] reversed and B a palindrome — or the mirror case.
That suggests looking words up reversed: a HashMap is the quickest to code; the trie walks each word once and handles every split together.
Call out the traps: the empty word, a word with its exact reverse, and never pairing a word with itself.

traps

Reporting a pair twice when a word and its reverse are both present — count the "whole word" split on one side only.
Pairing a palindrome word with itself (i == j).
Forgetting the empty word: it pairs with every palindrome, in both orders.

what they ask next

Follow-ups

LeetCode asks for O(sum of word lengths). How do you get there?

The extra factor of k comes from re-checking palindromes. Precompute, for each word, which of its prefixes and suffixes are palindromes in O(k) — Manacher's algorithm, or prefix hashes of the word and its reverse. Then each check is O(1) and the trie walk is linear in the total length.

before you submit

Edge cases to test

The empty word pairs with every palindrome word, in both orders.
A word and its exact reverse ("abcd", "dcba") → [i, j] and [j, i], each exactly once.
A palindrome word must never pair with itself (i ≠ j).

practise next