Palindrome Pairs

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(n k^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(n k) 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.

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.