To solve Palindrome Pairs, we combine array scanning with hash lookups to avoid the brute-force O(n^2*k) checks. By storing reversed words in a hash map and checking splits for palindromes, we quickly identify valid pairs. This method ensures we only scan necessary combinations and efficiently return all palindrome pairs in the array.
Problem Statement
You are given a 0-indexed array of unique strings words. Each word consists of lowercase English letters, and the array length ranges from 1 to 5000. Your task is to identify pairs of distinct indices where the concatenation of words forms a palindrome.
A palindrome pair is defined as a pair of integers (i, j) such that i != j and words[i] + words[j] is a palindrome. Return an array of all valid palindrome pairs, using an approach that avoids checking every two-word combination directly due to time constraints.
Examples
Example 1
Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]
Example 2
Input: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
The palindromes are ["battab","tabbat"]
Example 3
Input: words = ["a",""]
Output: [[0,1],[1,0]]
The palindromes are ["a","a"]
Constraints
- 1 <= words.length <= 5000
- 0 <= words[i].length <= 300
- words[i] consists of lowercase English letters.
Solution Approach
Use Hash Map for Reversed Words
Store each word's reverse in a hash map with its index. While scanning the array, check if any split of the current word matches a reversed word in the map, forming a palindrome pair. This leverages hash lookups for O(1) matching.
Split Words into Prefix and Suffix
For each word, iterate over all possible splits into prefix and suffix. Check if one part is a palindrome and the other part exists as a reversed word in the hash map. Add the corresponding indices to the result when both conditions satisfy palindrome formation.
Handle Edge Cases Like Empty Strings
Empty strings require special attention. Any non-empty palindrome can pair with an empty string in either order. Explicitly check for empty strings and combine with words that are palindromes to ensure no valid pair is missed.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(nk^2) in the worst case due to splitting each word (length k) and checking palindrome validity, but hash lookups reduce unnecessary comparisons. Space complexity is O(nk) for storing reversed words in the hash map.
What Interviewers Usually Probe
- Expect optimized solutions rather than brute-force O(n^2*k) pair checking.
- Watch for edge cases such as empty strings or single-character words forming palindromes.
- Clarify whether all returned pairs should be unique and correctly ordered by indices.
Common Pitfalls or Variants
Common pitfalls
- Checking every two-word combination without hash optimization, leading to TLE.
- Missing valid pairs involving empty strings or single-character palindromes.
- Forgetting to check both prefix and suffix splits when scanning words.
Follow-up variants
- Return only the count of palindrome pairs instead of the index pairs.
- Find palindrome pairs in a list where words may repeat and duplicates are allowed.
- Apply the same palindrome pair logic on a stream of incoming words efficiently.
How GhostInterview Helps
- Automatically identifies efficient split points and reversed word lookups to avoid brute-force failures.
- Highlights edge cases like empty strings or single-letter words, ensuring complete coverage of all palindrome pairs.
- Provides step-by-step array scanning and hash mapping guidance, turning complex checks into manageable operations.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main strategy for solving Palindrome Pairs efficiently?
Use array scanning combined with a hash map of reversed words, checking palindrome splits instead of brute-force pair comparisons.
How do empty strings affect palindrome pair results?
Any non-empty palindrome word can pair with an empty string in either order to form a valid palindrome pair.
Why not check every two-word combination directly?
Direct pair checks are O(n^2*k) and will exceed time limits for large arrays; hash-based splitting reduces complexity significantly.
Do we need to check both prefix and suffix splits of a word?
Yes, both prefix-palindrome/suffix-reverse and suffix-palindrome/prefix-reverse combinations can produce valid palindrome pairs.
Can this approach handle all word lengths up to 300 characters?
Yes, the algorithm efficiently handles long words using hash lookups and palindrome validation on splits without checking every pair.
Need direct help with Palindrome Pairs instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Palindrome Pairs from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Given a string and dictionary, return all possible sentences by adding spaces where each word is in the dictionary.
Open problem page#139 Word BreakDetermine if a string can be fully segmented into dictionary words using array scanning and hash-based lookups for efficiency.
Open problem page#648 Replace WordsReplace words in a sentence using the shortest root from a dictionary, applying efficient array scanning and hash lookup techniques.
Open problem page