Skip to main content
Talentd

Palindrome Pairs - Solution & Explanation

HardArrayHash TableStringTrie12 min readAsked at: Amazon, Microsoft, Goldman Sachs +5
Practice this problem

Problem Statement

You are 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, and
  • words[i] + words[j] (the concatenation of the two strings) is a palindrome.

Return an array of all the palindrome pairs of words.

You must write an algorithm with O(sum of words[i].length) runtime complexity.

 

Example 1:

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

Example 2:

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

Example 3:

Input: words = ["a",""]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["a","a"]

 

Constraints:

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

Approach Overview

Problem Overview: You are given a list of unique words. The task is to return all pairs of indices (i, j) such that concatenating words[i] + words[j] forms a palindrome. The challenge is efficiently checking many string combinations without recomputing palindrome checks repeatedly.

Approach 1: Brute Force Check with Reversed Strings (O(n2 * k) time, O(1) extra space)

The straightforward solution checks every ordered pair of words. For each pair (i, j), concatenate the two strings and verify if the result is a palindrome using two pointers from both ends. With n words and average length k, each concatenation check costs O(k), giving overall complexity O(n^2 * k). A small improvement is to precompute reversed versions of each string so you can quickly compare segments instead of building full concatenations. This approach relies mainly on simple array iteration and string comparison. It works well for small input sizes but quickly becomes slow when the number of words grows.

Approach 2: Using Trie Data Structure (O(n * k^2) time, O(n * k) space)

A more scalable approach builds a Trie containing reversed words. While inserting each reversed word, store indices of words whose remaining prefix forms a palindrome. This extra bookkeeping allows efficient matching later. When processing a word, iterate through its characters and walk the Trie simultaneously. If you encounter a Trie node that marks the end of another word and the remaining substring of the current word is a palindrome, you found a valid pair.

After reaching the end of the word in the Trie, any stored indices in that node represent words whose leftover suffix is already palindromic. Those indices also form valid pairs. This technique avoids comparing every pair directly and instead performs structured lookups. The Trie organizes reversed words by prefix, which makes matching efficient. The method combines concepts from Trie, hash table-style indexing, and repeated palindrome checks on substrings.

The key insight is splitting each word at every possible boundary. If the prefix is a palindrome, the reversed suffix may match another word. If the suffix is a palindrome, the reversed prefix may match. The Trie helps locate those matches quickly without scanning all words.

Recommended for interviews: Start with the brute force approach to show understanding of the problem and correctness of palindrome checks. Interviewers typically expect a more optimized design afterward. The Trie-based solution demonstrates stronger algorithmic thinking and knowledge of advanced string indexing techniques, which is why it is the preferred discussion in most senior-level interviews.

Approach 1: Brute Force Check with Reversed Strings

In this method, iterate through all possible pairs of words, concatenate them, and check if the concatenated result is a palindrome. Additionally, use the property that a string and its reverse can help identify palindrome pairs more efficiently.

The C solution uses a brute-force approach to find all possible pairs `(i, j)` and checks if their concatenation results in a palindrome. It does this by iterating over all matches and using a helper function `isPalindrome` to verify the condition.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2 * k)
Space Complexity: O(n^2)

Try this approach in the editor →

Approach 2: Using Trie Data Structure

Instead of brute force, we can utilize a Trie data structure to store word reversals, which allows faster lookup for potential palindrome content between pairs. This method improves efficiency by focusing on checks only where relevant.

This solution involves creating a Trie node structure to handle word entries with efficient searching capabilities.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * k^2)
Space Complexity: O(n * k)

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaGoC#

Python

Java

Go

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Check with Reversed Strings

Time Complexity: O(n^2 * k)
Space Complexity: O(n^2)

Using Trie Data Structure

Time Complexity: O(n * k^2)
Space Complexity: O(n * k)

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair CheckingO(n^2 * k)O(1)Good for understanding the problem or when the number of words is small
Trie with Reversed WordsO(n * k^2)O(n * k)Best for large inputs where checking all pairs is too slow

Video Solution

Palindrome Pairs | Leetcode 336 | Live coding session • Coding Decoded • 14,231 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Palindrome Pairs easy or hard?
Palindrome Pairs is classified as a Hard problem. The difficulty comes from combining multiple concepts: palindrome checking, substring partitioning, and efficient word lookup using structures like Trie.
How to solve Palindrome Pairs in O(n)?
A strict O(n) solution is not achievable because each word must be examined character by character. The closest practical optimization uses Trie or hash-based prefix and suffix checks, resulting in roughly O(n * k^2) time due to palindrome substring checks.
What is the best approach for Palindrome Pairs?
The most efficient practical solution uses a Trie storing reversed words along with palindrome suffix information. This allows quick prefix matching and avoids checking every pair directly. The typical complexity is O(n * k^2) time with O(n * k) space, where n is the number of words and k is the maximum word length.
What data structure is used in Palindrome Pairs?
Efficient solutions rely on a Trie to store reversed words and quickly match prefixes while scanning each word. Some variations also combine hash tables for direct reversed-string lookups and substring palindrome validation.
What is the time complexity of Palindrome Pairs?
The brute force method runs in O(n^2 * k) because it checks every pair of words and verifies whether their concatenation is a palindrome. The optimized Trie-based approach reduces comparisons and typically runs in O(n * k^2) time with O(n * k) memory.
Is Palindrome Pairs asked at Google, Amazon, or Meta?
Palindrome Pairs is considered a classic hard string problem and has appeared in interviews at large tech companies including Google, Amazon, and Meta. It tests knowledge of string manipulation, palindrome properties, and advanced data structures like Trie.
Is there a Python or Java solution for Palindrome Pairs?
Palindrome Pairs can be implemented in Python, Java, C++, and other languages. The logic typically involves building a Trie of reversed words or performing prefix-suffix palindrome checks with a hash map for quick lookups.

Ready to solve this problem?

Practice Palindrome Pairs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Maximum Number of String Pairs

Next

Longest Palindrome by Concatenating Two Letter Words