Log inSign up
hardLeetCodeNot Started

Palindrome Pairs

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trie
Solve on LeetCode
Lesson

Problem Statement

Given a 0-indexed array of unique strings words. A palindrome pair is a pair of integers (i, j) such that: - 0 <= i, j < words.length - i != j - words[i] + words[j] is a palindrome.

Return an array of all the palindrome pairs of words.

You must design an algorithm that runs in O(N * L2) time.

Example 1 · Example 1: Multiple palindrome pairs:

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

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the reversed-string Trie technique for suffix-prefix alignment.
  • Cache palindrome properties directly inside Trie nodes during insertion.
  • Decompose palindrome concatenation into two complementary prefix/suffix cases.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Concatenating pairs of strings to check if the combined string is a palindrome.
  • Need all valid index pairs (i, j) with i \neq j.
  • Prefixes and suffixes of variable lengths interact.

Algorithmic Decision Tree:

  • Insert REVERSED words into a Trie.
  • Each TrieNode stores wordIndex = -1 and a vector palindromeSuffixes.
  • During insertion of reversed w_j, if suffix w_j[0..k] is a palindrome, add j to node.palindromeSuffixes.

Connected Patterns:

Shortest PalindromeLongest Palindromic SubstringImplement Trie

1. All Pairs String Concatenation

Intuition

Two nested loops generating all pairs. Concatenate words[i] + words[j] and run a two-pointer check. Add [i, j] if valid.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Loop i from 0 to N-1.
  2. Step 2: Loop j from 0 to N-1: if i == j, continue.
  3. Step 3: Check if words[i] + words[j] is a palindrome.
  4. Step 4: If yes, add [i, j] to output list.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4using namespace std;
5
6class Solution {
7 bool isPalindrome(const string& s) {
8 int l = 0, r = s.length() - 1;
9 while (l < r) {
10 if (s[l++] != s[r--]) return false;
11 }
12 return true;
13 }
14
15public:
16 vector<vector<int>> palindromePairs(vector<string>& words) {
17 vector<vector<int>> result;
18 int n = words.size();
19 for (int i = 0; i < n; i++) {
20 for (int j = 0; j < n; j++) {
21 if (i == j) continue;
22 if (isPalindrome(words[i] + words[j])) {
23 result.push_back({i, j});
24 }
25 }
26 }
27 return result;
28 }
29};
30
31int main() {
32 Solution sol;
33 vector<string> words = {"abcd","dcba","lls","s","sssll"};
34 auto res = sol.palindromePairs(words);
35 for (const auto& p : res) cout << "[" << p[0] << "," << p[1] << "] ";
36 cout << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N^2 * L) — N2 pairs each taking O(L) to concatenate and verify.
  • Space complexity: O(L) — Allocates combined string.

Why Brute Force Doesn't Scale:

N = 5,000 creates 25,000,000 pairs, exceeding time limits by 100x.

Reversed Trie with cached palindrome suffixes processes all 5,000 words in O(N * L2) ~ 50ms.

2. Hash Map Prefix/Suffix Cut Slicing

Intuition

Map reversedWord -> index. For each word w_i, split into prefix w_i[0..k] and suffix w_i[k..len]. If prefix is a palindrome and remaining suffix is in map, form pair. If suffix is a palindrome and remaining prefix is in map, form pair.

When to apply: When avoiding pointer Trie structures is preferred.

Algorithm

  1. Step 1: Map reversed strings to their word index.
  2. Step 2: For each word w_i and each cut point k from 0 to w_i.length():
  3. Step 3: If prefix is palindrome, check if reversed suffix exists in map.
  4. Step 4: If suffix is palindrome, check if reversed prefix exists in map.
  5. Step 5: Deduplicate and append valid pairs.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include <algorithm>
6using namespace std;
7
8class Solution {
9 bool isPalindrome(const string& s, int l, int r) {
10 while (l < r) {
11 if (s[l++] != s[r--]) return false;
12 }
13 return true;
14 }
15
16public:
17 vector<vector<int>> palindromePairs(vector<string>& words) {
18 unordered_map<string, int> wordMap;
19 for (size_t i = 0; i < words.size(); i++) {
20 wordMap[words[i]] = i;
21 }
22
23 vector<vector<int>> result;
24 int n = words.size();
25
26 for (int i = 0; i < n; i++) {
27 string w = words[i];
28 int len = w.length();
29
30 for (int k = 0; k <= len; k++) {
31 // If prefix is palindrome, find reversed suffix
32 if (isPalindrome(w, 0, k - 1)) {
33 string rem = w.substr(k);
34 reverse(rem.begin(), rem.end());
35 if (wordMap.count(rem) && wordMap[rem] != i) {
36 result.push_back({wordMap[rem], i});
37 }
38 }
39 // If suffix is palindrome, find reversed prefix
40 if (k < len && isPalindrome(w, k, len - 1)) {
41 string rem = w.substr(0, k);
42 reverse(rem.begin(), rem.end());
43 if (wordMap.count(rem) && wordMap[rem] != i) {
44 result.push_back({i, wordMap[rem]});
45 }
46 }
47 }
48 }
49 return result;
50 }
51};
52
53int main() {
54 Solution sol;
55 vector<string> words = {"abcd","dcba","lls","s","sssll"};
56 auto res = sol.palindromePairs(words);
57 for (const auto& p : res) cout << "[" << p[0] << "," << p[1] << "] ";
58 cout << endl;
59 return 0;
60}

Time & Space Complexity

  • Time complexity: O(N * L^2) — For N words of length L, testing all cut points takes O(L2) substring operations.
  • Space complexity: O(N * L) — Hash map stores all N reversed words.

3. Reversed Trie with Palindrome Suffix Cache

Intuition

Insert each word into the Trie in reverse. At each node during insertion, check if the remaining uninserted prefix forms a palindrome; if so, append word index to node.palindromeSuffixes. For search: for word w_i, walk the Trie. At each step, if a word terminates here and the rest of w_i is a palindrome, add pair (i, j). When w_i finishes, all cached palindromeSuffixes at current node form pairs (i, k).

When to apply: Standard optimal solution with structural elegance and no string slicing during search.

Algorithm

  1. Step 1: Define TrieNode with children[26], wordIndex = -1, palindromeSuffixes list.
  2. Step 2: Helper isPalindrome(s, l, r).
  3. Step 3: insert(word, idx): walk reversed word. If isPalindrome(word, 0, j), add idx to curr.palindromeSuffixes. Move to child. At end, set curr.wordIndex = idx.
  4. Step 4: search(word, idx): walk word forward. If curr.wordIndex != -1 && curr.wordIndex != idx && isPalindrome(word, j, len-1), add pair [idx, curr.wordIndex]. When word finishes, add all pIdx from curr.palindromeSuffixes (where pIdx != idx) as [idx, pIdx].

Interactive Trace for Reversed Trie Palindrome Matching

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Insert reversed 'lls' ('s' -> 'l' -> 'l') into Trie
Visual state
Values and pointers at this exact step
tree
Root
(root)
char 's'
palList: [0]
char 'l'
'l'
char 'l'*
word 0 ('lls')

Node order shown; add connections to display explicit tree edges.

cache [0]: s
Check / comparison
'll' is palindrome -> add index 0 to node 's'
Decision / next transition
Node 's' caches word 0 as palindrome suffix.
Why this step matters

Step 1: Insert reversed lls (s -> l -> l) into Trie. At node s, remaining suffix is ll, which is a palindrome. Record index 0 in node s palindrome list.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4using namespace std;
5
6struct TrieNode {
7 TrieNode* children[26];
8 int wordIndex;
9 vector<int> palindromeSuffixes;
10
11 TrieNode() : wordIndex(-1) {
12 for (int i = 0; i < 26; i++) children[i] = nullptr;
13 }
14};
15
16class Solution {
17 TrieNode* root;
18
19 bool isPalindrome(const string& s, int l, int r) {
20 while (l < r) {
21 if (s[l++] != s[r--]) return false;
22 }
23 return true;
24 }
25
26 void insert(const string& word, int idx) {
27 TrieNode* curr = root;
28 int len = word.length();
29 for (int i = len - 1; i >= 0; i--) {
30 if (isPalindrome(word, 0, i)) {
31 curr->palindromeSuffixes.push_back(idx);
32 }
33 int c = word[i] - 'a';
34 if (!curr->children[c]) curr->children[c] = new TrieNode();
35 curr = curr->children[c];
36 }
37 curr->wordIndex = idx;
38 curr->palindromeSuffixes.push_back(idx);
39 }
40
41public:
42 vector<vector<int>> palindromePairs(vector<string>& words) {
43 root = new TrieNode();
44 int n = words.size();
45 for (int i = 0; i < n; i++) insert(words[i], i);
46
47 vector<vector<int>> result;
48
49 for (int i = 0; i < n; i++) {
50 const string& w = words[i];
51 TrieNode* curr = root;
52 int len = w.length();
53
54 for (int j = 0; j < len; j++) {
55 if (curr->wordIndex != -1 && curr->wordIndex != i && isPalindrome(w, j, len - 1)) {
56 result.push_back({i, curr->wordIndex});
57 }
58 int c = w[j] - 'a';
59 if (!curr->children[c]) {
60 curr = nullptr;
61 break;
62 }
63 curr = curr->children[c];
64 }
65
66 if (curr) {
67 for (int pIdx : curr->palindromeSuffixes) {
68 if (pIdx != i) {
69 result.push_back({i, pIdx});
70 }
71 }
72 }
73 }
74 return result;
75 }
76};
77
78int main() {
79 Solution sol;
80 vector<string> words = {"abcd","dcba","lls","s","sssll"};
81 auto res = sol.palindromePairs(words);
82 for (const auto& p : res) cout << "[" << p[0] << "," << p[1] << "] ";
83 cout << endl;
84 return 0;
85}

Time & Space Complexity

  • Time complexity: O(N * L^2) — Precomputing palindromes takes O(L) per node, total O(N * L2). Querying each word takes O(L2) palindrome checks.
  • Space complexity: O(N * L) — Trie nodes store pointers and integer indices.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Check All PairsO(N^2 * L)O(L)Two nested loops checking if isPalindrome(words[i] + words[j]) for all pairs.All pairs string concatenation and verification.
2.Better — Hash Map Suffix/Prefix PartitioningO(N * L^2)O(N * L)Store words in a hash map. For each word, split into prefix and suffix at all L cut points. If prefix is palindrome, look up reversed suffix; if suffix is palindrome, look up reversed prefix.Heap string slicing at every cut point.
3.Optimal — Reversed Trie with Palindrome Suffix CacheOptimalO(N * L^2)O(N * L)Insert words in reverse into Trie. Precalculate palindrome suffixes at each node. Single traversal per word discovers all matching partner pairs.None. Canonical gold-standard solution for Palindrome Pairs.

Common Pitfalls & Crucial Edge Cases

Missing empty string palindromes

Empty string paired with palindrome string must produce two pairs (i, empty) and (empty, i).

Pairing a word with itself (i == j)

Self-pairs are prohibited by definition i != j.

Inserting words forward instead of reversed

Palindrome partner matching requires walking reversed words.

Crucial Edge Cases to Validate:

  • Empty string present in words — Pairs with every word that is itself a palindrome in both directions: [i, empty_idx] and [empty_idx, i].
  • Pair of identical reversed strings ('abcd' and 'dcba') — Forms both [0, 1] and [1, 0].
  • Single letter words ('a', 'b') — Pairs with nothing unless matching or empty string present.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the two fundamental cases clearly: (1) current word is longer than partner; (2) current word is shorter than partner.
  2. Highlight the key optimization: storing palindromeSuffixes during insertion avoids traversing subtrees during search.
  3. Mention that reversed Trie + index caching drops query time to linear in word length O(L2).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why are words inserted REVERSED into the Trie for the Palindrome Pairs problem?

2.What does the list palindromeSuffixes store at each Trie node?

Back to DSA Sheet