Palindrome Pairs
Hard · Tries · Array · Hash Table · String · Trie
Problem
You are given an array of unique strings words. A palindrome pair is a pair of indices (i, j) with i != j such that the concatenation words[i] + words[j] reads the same forwards and backwards.
Return all palindrome pairs [i, j], in any order. [i, j] and [j, i] are different pairs, and each is included only if its own concatenation is a palindrome.
Checking every pair costs O(n² · L). Aim for time proportional to the total length of the words times the word length: split each word at every position and look up the reverse of one part.
Examples
Input: words = ["ab","ba","abb","c"] Output: [[0,1],[1,0],[2,1]]
"abba", "baab" and "abbba" are palindromes; "c" pairs with nothing.
Input: words = ["","aba","x"] Output: [[0,1],[0,2],[1,0],[2,0]]
The empty string can go on either side of the palindromes "aba" and "x".
Constraints
- 1 <= len(words) <= 5000
- 0 <= len(words[i]) <= 300
- words[i] consists of lowercase English letters
- All the words are different
Approaches
- Baseline: test every ordered pair — time O(n² · L), space O(L)
Follow-up
What if words could repeat, and you only needed the number of pairs? Count the words, run the same splits over the distinct ones, and multiply each match by the counts (see the use case “Count the pairs when words can repeat”).
Related problems
Start free on Cariara · Coding problems · System design studio
