Introduction
Palindrome-related problems are among the most common interview questions because they combine string manipulation, hashing, and optimization techniques.
In this problem, we are given an array of strings and must determine whether there exists a pair of different indices (i, j) such that:
arr[i] + arr[j]
forms a palindrome.
The challenge is to find such a pair efficiently without checking every possible combination.
Problem Statement
Given an array of strings:
arr[]
Determine whether there exists a pair of indices:
i ≠ j
such that:
arr[i] + arr[j]
is a palindrome.
Return:
true
if such a pair exists; otherwise, return:
false
Example 1
Input
["geekf", "geeks", "or", "keeg", "abc", "bc"]
Pair Found
geekf + keeg
=
geekfkeeg
Reverse:
geekfkeeg
Same forward and backward.
Output
true
Example 2
Input
["abc", "xyxcba", "geekst", "or", "bc"]
Pair Found
abc + xyxcba
=
abcxyxcba
This is a palindrome.
Output
true
Example 3
Input
["aa"]
Only one string exists.
No valid pair:
i ≠ j
cannot be satisfied.
Output
false
Naive Approach
A straightforward solution is:
Pseudocode
for every i
for every j
if i != j
check arr[i] + arr[j]
Complexity
O(n² × l)
where:
n = number of strings
l = string length
For:
n = 20000
this becomes too slow.
Key Observation
Suppose:
word = "abc"
Reverse:
"cba"
If another word equals:
"cba"
then:
abc + cba
becomes:
abccba
which is a palindrome.
This suggests storing strings in a hash map for quick reverse lookups.
An Even Better Observation
Consider:
word = "abcd"
Split at every position.
Split 1
"" | abcd
Split 2
a | bcd
Split 3
ab | cd
Split 4
abc | d
Split 5
abcd | ""
For every split, we examine:
We check whether one side is already a palindrome.
If yes, we only need to find the reverse of the other side.
Why This Works
Suppose:
word = "abc"
Split:
a | bc
Left part:
"a"
is already a palindrome.
If the reverse of:
"bc"
which is:
"cb"
exists in the array, then:
cb + abc
forms a palindrome.
HashMap Optimization
Store every string in:
Map<String,Integer> map
Example:
abc → 0
cba → 1
xyx → 2
Now every reverse lookup becomes:
O(1)
Algorithm
Step 1
Try every possible split.
left = word[0...i-1]
right = word[i...end]
Step 2
If left is a palindrome:
Search for:
reverse(right)
in the HashMap.
Step 3
If right is a palindrome:
Search for:
reverse(left)
in the HashMap.
Step 4
If found and the index differs:
return true
Step 5
After checking all words:
return false
Example Walkthrough
Input
["abc","cba"]
HashMap
abc → 0
cba → 1
Processing
word = abc
Split:
abc | ""
Right side:
""
is a palindrome.
Reverse of left:
cba
exists.
Different index:
1 ≠ 0
Return:
true
Java Solution
class Solution {
private boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right))
return false;
left++;
right--;
}
return true;
}
public boolean palindromePair(String[] arr) {
HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
map.put(arr[i], i);
}
for (int i = 0; i < arr.length; i++) {
String word = arr[i];
for (int cut = 0; cut <= word.length(); cut++) {
String left = word.substring(0, cut);
String right = word.substring(cut);
// Case 1
if (isPalindrome(left)) {
String revRight =
new StringBuilder(right)
.reverse()
.toString();
Integer idx = map.get(revRight);
if (idx != null && idx != i) {
return true;
}
}
// Case 2
if (cut != word.length() &&
isPalindrome(right)) {
String revLeft =
new StringBuilder(left)
.reverse()
.toString();
Integer idx = map.get(revLeft);
if (idx != null && idx != i) {
return true;
}
}
}
}
return false;
}
}
Dry Run
Input
["abc","cba"]
HashMap
abc → 0
cba → 1
Processing
abc
Split:
abc | ""
Right:
""
Palindrome:
Yes
Reverse of left:
cba
Found in map:
Index = 1
Different from current index:
1 != 0
Return:
true
Complexity Analysis
Let:
n = number of strings
l = maximum string length
Time Complexity
For every word:
l splits
For each split:
Palindrome check = O(l)
Total:
O(n × l²)
Space Complexity
HashMap stores all strings:
O(n × l)
Additional reverse strings and substrings:
O(n × l²)
which matches the expected complexity.
Why This Solution Is Optimal
The brute-force solution compares every pair:
O(n²)
which is impractical for:
n = 20000
Using:
reduces the complexity to:
O(n × l²)
which is the expected solution for this problem.
Conclusion
The Palindrome Pairs problem is a classic interview question that combines:
The key insight is that for a concatenation to become a palindrome, one part must already be a palindrome while the reverse of the remaining part exists elsewhere in the array.
By using a HashMap and checking all possible splits of each word, we achieve an efficient solution with:
Time Complexity: O(n × l²)
Space Complexity: O(n × l²)
making it suitable for large inputs and coding interviews.