DSA problem
Palindrome Pairs
Given a 0-indexed array of unique strings words, return an array of all the palindrome pairs of distinct indices [i, j] such that words[i] + words[j] is a palindrome.
The brute-force solution checks every ordered pair (i, j) with i != j and tests whether words[i] + words[j] is a palindrome. With N words of length up to L, that costs O(N^2 * L) — far too slow when N is in the tens of thousands.
The optimal approach uses a hash map from each word to its index. The key insight is to enumerate splits: for every word w and every split position k, consider prefix = w[:k] and suffix = w[k:]. If prefix is a palindrome AND the reverse of suffix exists in the map at index j != i, then concatenating words[j] in front of w produces a palindrome — i.e. (j, i) is a valid pair. Symmetrically, if suffix is a palindrome AND the reverse of prefix exists at index j != i, then (i, j) is a valid pair.
This split-and-check strategy needs careful handling of duplicate work at the empty-prefix split to avoid emitting each pair twice. The final complexity is O(N * L^2) time and O(N * L) space, which scales well even on the largest inputs in the problem range.
Examples
words = ["abcd","dcba","lls","s","sssll"][[0,1],[1,0],[3,2],[2,4]]words = ["bat","tab","cat"][[0,1],[1,0]]words = ["a",""][[0,1],[1,0]]Constraints
- 1 <= words.length <= 5000
- 0 <= words[i].length <= 300
- words[i] consists of lowercase English letters.
4 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.