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.

Description Hints 3 Solution Video 10:47

336. Palindrome Pairs

Hard37.7% acceptance8 companies

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.

Asked at 8 companies

Airbnb Wix Expedia

Google Goldman Sachs Amazon Microsoft Meta

Topics

Hints open one at a time

Hint 1

Checking every two pairs will exceed the time limit. It will be O(n^2 * k). We need a faster way.

Hint 2

If we hash every string in the array, how can we check if two pairs form a palindrome after the concatenation?

Hint 3

We can check every string in words and consider it as words[j] (i.e., the suffix of the target palindrome). We can check if there is a hash of string that can be the prefix to make it a palindrome.

10:47

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution