Palindrome pairs with a reversed-word trie

Why this matters

A palindrome is text that reads the same forwards and backwards. level is a palindrome. racecar is one too. cat is not.

A common interview question combines this with a list of words. Given a list of words, find every pair that forms a palindrome when one word is placed directly after the other.

The simple method checks every ordered pair. It joins word i and word j, then tests whether the joined text is a palindrome. With 1,000 words there are 999,000 ordered pairs, and each test may read the whole joined text. Most pairs fail on their first few letters, so most of that work is wasted. A trie, which is a tree of letters, lets you skip the failing pairs without testing them one by one.

This lesson builds on the first lesson of this module, which introduces the trie structure. Here the trie holds reversed words, and each word is looked up by walking it forwards.

Words used in this lesson

Palindrome: text that reads the same forwards and backwards. abba and a are palindromes. ab is not. The empty text also counts as a palindrome.
Reverse: the same letters in the opposite order. The reverse of bat is tab.
Pair: two different words in a fixed order. The pair (0, 2) means the word at position 0 comes first and the word at position 2 comes second. Positions start at 0.
Joined text: one word placed directly after another. Joining ab and a gives aba.
Prefix: the first few letters of a word. ca is a prefix of cat.
Trie: a tree of letters. Each step down the tree adds one letter, so each path from the top (the root) spells a prefix.

Order matters. ab followed by a gives aba, which is a palindrome. a followed by ab gives aab, which is not. So the pairs (0, 1) and (1, 0) must be checked separately.

A first example with the simple method

Take three words at positions 0, 1 and 2: bat, tab and cat. Join each ordered pair and test it.

bat then tab gives battab. Read backwards, it is still battab. This is a pair, (0, 1).
tab then bat gives tabbat. Read backwards, it is still tabbat. This is a pair, (1, 0).
bat then cat gives batcat. Read backwards, it is tactab. Not a pair.
cat then bat gives catbat. Read backwards, it is tabtac. Not a pair.
tab then cat gives tabcat. Read backwards, it is tacbat. Not a pair.
cat then tab gives cattab. Read backwards, it is battac. Not a pair.

So the answer is (0, 1) and (1, 0). The next sections show how to find the same answer without testing all six joins.

The key idea: each pair splits at a middle

Suppose the first word is a, the second word is b, and the joined text a then b is a palindrome. Then the longer word starts or ends with the reverse of the shorter word. There are two cases.

Case 1: the first word is at least as long

Take the first word sll and the second word s. Joined, they give slls, which is a palindrome.

The first word starts with s, and that is the reverse of the second word s. What remains of the first word after that start is ll. The leftover ll is a palindrome.

This always works in the same way. The first word is the reverse of the second word, followed by a palindrome. Call the palindrome m. The joined text has three parts: the reverse of the second word, then m, then the second word. Read backwards, those three parts come out as the reverse of the second word, then m, then the second word again. That is the same text, so the joined text is a palindrome.

Case 2: the first word is shorter

Take the first word s and the second word lls. Joined, they give slls again.

The second word ends with s, which is the reverse of the first word. The letters before that ending are ll, a palindrome.

This is the mirror image of case 1. The second word is a palindrome followed by the reverse of the first word. Joined, the text is the first word, then the palindrome, then the reverse of the first word. Read backwards, it is the same text.

A pair of equal length

If both words have the same length, the leftover palindrome is empty, and both cases describe the same pair. For example, abcd followed by dcba gives abcddcba. The first word is the reverse of the second word, with nothing left over.

Turning both cases into one lookup

In both cases, one word starts with the reverse of the other, and any leftover letters form a palindrome. So you can store every word reversed in a trie, then walk each word forwards through that trie.

Here is why the walk works for each case.

In case 1, the first word starts with the reverse of the second word. The walk follows the reversed second word down the trie, and it reaches the end of that reversed word.
In case 2, the second word is a palindrome followed by the reverse of the first word. Reversed, the second word becomes the first word followed by a palindrome. So the walk of the first word ends at one node, and the stored word sits below that node with a palindrome left over.

This leads to two checks made during the walk.

Check A (case 1). At each step of the walk, if a reversed word ends at this node, the letters of the walked word that come after this point must form a palindrome. If they do, the walked word and that stored word form a pair.
Check B (case 2). When the walk has used every letter of the walked word, each word stored below this node is a candidate. A stored word is a pair with the walked word if the leftover letters of its reversed text form a palindrome.

Check B needs a quick answer at each node, so the trie stores that answer ahead of time. For each node, it keeps a list of the words whose reversed text has a palindrome beginning just after that node. Building this list takes some work when the trie is built, but the walk then only reads the list.

Worked example: three words, four pairs

Use these words, at positions 0, 1 and 2: lls, s and sll.

Step 1: store the reversed words

Reverse each word and insert it into the trie.

Word 0, lls, is stored as sll.
Word 1, s, is stored as s.
Word 2, sll, is stored as lls.

While inserting, each node records which words have a palindrome beginning there. For the reversed word sll (word 0), the leftover after one letter is ll, a palindrome. So the node for s records word 0. After two letters, the leftover is l, also a palindrome, so the node for sl records word 0 too. After three letters, the leftover is empty, which counts as a palindrome. So the node for sll records word 0.

Word 1 is stored as s. Its leftover after zero letters is s, a palindrome, so the root records word 1. After one letter the leftover is empty, so the node for s also records word 1.

Word 2 is stored as lls. Its leftover after two letters is s, a palindrome, so the node for ll records word 2. After three letters the leftover is empty, so the node for lls records word 2.

The nodes used in the walk below end up with these lists:

The node for s lists words 0 and 1.
The node for sll lists word 0.
The node for lls lists word 2.

Word 1 also ends at the node for s, and word 0 ends at the node for sll. Word 2 ends at the node for lls.

Step 2: walk word 0, `lls`

Start at the root. No word ends there. The first letter of lls is l, so go down the l branch.
The node for l has no word end. The next letter is l, so go down to ll.
The node for ll has no word end. The next letter is s, so go down to lls.
All three letters are used. The node for lls lists word 2. Pair (0, 2): lls then sll gives llssll, which is a palindrome.

Step 3: walk word 1, `s`

Start at the root. No word ends there. The first letter is s, so go down to the node for s.
All letters are used. The node for s lists words 0 and 1. Word 1 is the word itself, so skip it. Word 0 gives pair (1, 0): s then lls gives slls.

Step 4: walk word 2, `sll`

Start at the root. No word ends there. The first letter is s, so go down to the node for s.
The node for s ends word 1, which is s. Check A: the letters of sll after one letter are ll, a palindrome. Pair (2, 1): sll then s gives slls.
The next letter is l, so go down to sl. It has no word end. The next letter is l, so go down to sll.
All letters are used. The node for sll lists word 0. Pair (2, 0): sll then lls gives sllls, which is a palindrome.

The four pairs are (0, 2), (1, 0), (2, 1) and (2, 0). The program below prints the same four pairs.

The code

The program reads a count, then that many words separated by spaces. It prints each pair as two positions on one line, in sorted order.

Input for the first run:

5
abcd dcba lls s sssll

C++ · editable

#include <algorithm>
#include <array>
#include <iostream>
#include <memory>
#include <string>
#include <utility>
#include <vector>
using namespace std;

struct Node {
    array<unique_ptr<Node>, 26> child{};
    vector<int> wordEnds;
    vector<int> palSuffix;
};

// True when s[lo..hi] reads the same forwards and backwards.
// An empty range (lo greater than hi) counts as a palindrome.
bool isPal(const string& s, int lo, int hi) {
    while (lo < hi) {
        if (s[lo] != s[hi]) return false;
        ++lo;
        --hi;
    }
    return true;
}

vector<pair<int, int>> palindromePairs(const vector<string>& words) {
    Node root;

// Store each word reversed.
    for (int idx = 0; idx < (int)words.size(); ++idx) {
        const string r(words[idx].rbegin(), words[idx].rend());
        const int n = (int)r.size();
        Node* cur = &root;
        for (int d = 0; d <= n; ++d) {
            if (isPal(r, d, n - 1)) cur->palSuffix.push_back(idx);
            if (d == n) {
                cur->wordEnds.push_back(idx);
                break;
            }
            auto& slot = cur->child[r[d] - 'a'];
            if (!slot) slot = make_unique<Node>();
            cur = slot.get();
        }
    }

// Walk each word forwards through the reversed-word trie.
    vector<pair<int, int>> out;
    for (int i = 0; i < (int)words.size(); ++i) {
        const string& w = words[i];
        const int n = (int)w.size();
        const Node* cur = &root;
        bool reached = true;
        for (int d = 0; d < n; ++d) {
            if (isPal(w, d, n - 1))
                for (int j : cur->wordEnds) out.push_back({i, j});
            const auto& next = cur->child[w[d] - 'a'];
            if (!next) {
                reached = false;
                break;
            }
            cur = next.get();
        }
        if (reached) {
            for (int j : cur->palSuffix)
                if (j != i) out.push_back({i, j});
        }
    }
    sort(out.begin(), out.end());
    return out;
}

int main() {
    int n;
    cin >> n;
    vector<string> words(n);
    for (string& w : words) cin >> w;

for (auto [i, j] : palindromePairs(words)) {
        cout << i << " " << j << "\n";
    }
}

Output:

The output lists the pairs in the order (0, 1), (1, 0), (2, 4), (3, 2). Check one of the last two: word 2 is lls and word 4 is sssll. Joined, they give llssssll, which reads the same both ways.

Read the code in three parts.

Node holds up to 26 children, one for each letter. Each child is a unique_ptr, which owns the child node and frees it when the trie goes away. wordEnds lists the positions of the words that end at this node. It holds more than one entry only when the input repeats a word. palSuffix is the palindrome list described above.
The first loop inserts each reversed word. At each depth d, it records the word in palSuffix if the leftover letters form a palindrome. The d == n branch marks the end of the word.
The second loop walks each word forwards. Check A runs at each step, before the walk moves on. Check B runs once at the end, if the walk did not fall off the trie. The test j != i stops a word from pairing with itself.

Complexity and limits

Let n be the number of words and k the length of the longest word.

Building the trie. Each word adds up to k nodes. At each depth, isPal may read up to k letters, so one word costs up to about k times k steps. The total is the sum of that over all words.
Walking. Each word is walked once, which is up to k steps. Each step may also call isPal, so the walk costs up to about k times k steps per word.
Output. The list of pairs can be very large. If every word is a, aa, aaa and so on, almost every ordered pair is a palindrome, so the output has about n times n pairs. No method can print that many pairs faster than writing them out.

The isPal check is the weak spot. It reads letters one by one, so long words are slower than they need to be. A faster palindrome test, such as Manacher's algorithm, would cut that cost. This lesson keeps the simple test so the trie logic stays easy to read. For the short words in typical tests, the simple test is fast enough.

Common mistakes

Pairing a word with itself. A palindrome such as a reversed is still a, so it reaches its own palindrome list. If the program does not skip j != i, it prints a pair with itself. For the input 2 and a b, the output with that skip removed is this.

0 0
1 1

Word 0 would be joined with itself, giving aa, even though the input has only one copy of a. The fix is the j != i test in the final loop.

Forgetting check A. Check A handles pairs where the walked word is longer than the stored word. If you remove it, the pairs with a longer first word go missing. For the input 3 and lls s sll, the correct output includes 2 1, which joins sll and s into slls. Without check A, the output is this.

0 2
1 0
2 0

Forgetting check B. Check B handles pairs where the first word is shorter. If you remove the palSuffix loop, the pairs with a shorter first word go missing. For the same input, the output is only this.

2 1

Storing words without reversing them. If the trie holds the words as they are, the walk looks for the wrong prefixes. For the input 3 and bat tab cat, the program prints nothing. The correct output is 0 1 and 1 0.

Keeping one word per node. Two equal input words reverse to the same text, so they share one node. A version that keeps one word number per node loses the other copy. For the input 3 and bac ab ab, that version prints only 0 2, and the correct output is 0 1 and 0 2.

Copying a node. Each Node owns its children through unique_ptr, and a unique_ptr cannot be copied. A line such as Node copy = root; fails to compile. The error message in g++ 15 starts like this.

copyerr.cpp:11:17: error: use of deleted function 'Node::Node(const Node&)'
   11 |     Node copy = root;
      |                 ^~~~

Pass a Node by pointer or by reference instead. The code above never copies a node.

Letters outside a to z. The code uses c - 'a' to choose one of 26 slots. A capital letter or a digit gives a negative or too-large index. That is undefined behaviour in C++, so the program may crash or give wrong answers. The problem promises lowercase letters, and the code relies on that promise.

Practice

Exercise 1. Predict the output for the input 2 and ab a. Check your answer by joining each ordered pair.

Show the answer

The output is 0 1. The joined text ab then a is aba, a palindrome. The joined text a then ab is aab, which is not.

Exercise 2. Predict the output for the input 2 and a aa.

Show the answer

The output is 0 1 and 1 0. Both a then aa (which is aaa) and aa then a (which is aaa) are palindromes.

Exercise 3. Predict the output for the input 3 and aba ab ba. Work out each ordered pair by hand.

Show the answer

The output is 0 2, 1 0, 1 2 and 2 1. The joins are these.

aba then ab gives abaab. Not a palindrome.
aba then ba gives ababa. A pair, (0, 2).
ab then aba gives ababa. A pair, (1, 0).
ab then ba gives abba. A pair, (1, 2).
ba then aba gives baaba. Not a palindrome.
ba then ab gives baab. A pair, (2, 1).

Exercise 4. For the input 3 and lls s sll, the program prints 0 2, 1 0, 2 0 and 2 1. Suppose you delete check A from the code. Which line of output disappears, and why?

Show the answer

The line 2 1 disappears. Pair (2, 1) joins sll (the first word, longer) with s (the second word, shorter). That is the case where check A is needed, because the first word is longer than the stored word it matches.

Exercise 5. The walk uses each word forwards, but the trie stores the words reversed. Explain in plain words why the walk uses forwards letters.

Show the answer

The two cases both say that a word starts with the reverse of another word. If the trie stores reversed words, then reading the walked word forwards matches the start of a reversed stored word. Reading the walked word backwards would match the wrong end of the stored word, and the palindrome leftovers would be in the wrong place.

Summary

A pair (a, b) forms a palindrome only if one word starts with the reverse of the other, and the letters left over form a palindrome.
Storing reversed words in a trie turns both cases into a walk of one word forwards through the trie.
Check A looks for a stored word that ends during the walk, with a palindrome left over. Check B looks at the list of palindrome leftovers at the end of the walk.
The j != i test stops a word from pairing with itself, and both checks are needed to find every pair.
The simple palindrome test makes long words slow. A faster test would help, but the trie logic stays the same.

Palindrome pairs with a reversed-word trie

Why this matters

Words used in this lesson

A first example with the simple method

The key idea: each pair splits at a middle

Case 1: the first word is at least as long

Case 2: the first word is shorter

A pair of equal length

Turning both cases into one lookup

Worked example: three words, four pairs

Step 1: store the reversed words

Step 2: walk word 0, lls

Step 3: walk word 1, s

Step 4: walk word 2, sll

The code

Complexity and limits

Common mistakes

Practice

Summary

Stuck? Ask the tutor

Step 2: walk word 0, `lls`

Step 3: walk word 1, `s`

Step 4: walk word 2, `sll`