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:

Code
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:

Code
arr[]

Determine whether there exists a pair of indices:

Code
i ≠ j

such that:

Code
arr[i] + arr[j]

is a palindrome.

Return:

Code
true

if such a pair exists; otherwise, return:

Code
false

Example 1

Input

Code
["geekf", "geeks", "or", "keeg", "abc", "bc"]

Pair Found

Code
geekf + keeg
=
geekfkeeg

Reverse:

Code
geekfkeeg

Same forward and backward.

Output

Code
true

Example 2

Input

Code
["abc", "xyxcba", "geekst", "or", "bc"]

Pair Found

Code
abc + xyxcba
=
abcxyxcba

This is a palindrome.

Output

Code
true

Example 3

Input

Code
["aa"]

Only one string exists.

No valid pair:

Code
i ≠ j

cannot be satisfied.

Output

Code
false

Naive Approach

A straightforward solution is:

Pseudocode

Code
for every i
    for every j
        if i != j
            check arr[i] + arr[j]

Complexity

Code
O(n² × l)

where:

For:

Code
n = 20000

this becomes too slow.

Key Observation

Suppose:

Code
word = "abc"

Reverse:

Code
"cba"

If another word equals:

Code
"cba"

then:

Code
abc + cba

becomes:

Code
abccba

which is a palindrome.

This suggests storing strings in a hash map for quick reverse lookups.

An Even Better Observation

Consider:

Code
word = "abcd"

Split at every position.

Split 1

Code
"" | abcd

Split 2

Code
a | bcd

Split 3

Code
ab | cd

Split 4

Code
abc | d

Split 5

Code
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:

Code
word = "abc"

Split:

Code
a | bc

Left part:

Code
"a"

is already a palindrome.

If the reverse of:

Code
"bc"

which is:

Code
"cb"

exists in the array, then:

Code
cb + abc

forms a palindrome.

HashMap Optimization

Store every string in:

Java
Map<String,Integer> map

Example:

Code
abc → 0
cba → 1
xyx → 2

Now every reverse lookup becomes:

Code
O(1)

Algorithm

Step 1

Try every possible split.

Code
left = word[0...i-1]
right = word[i...end]

Step 2

If left is a palindrome:

Search for:

Code
reverse(right)

in the HashMap.

Step 3

If right is a palindrome:

Search for:

Code
reverse(left)

in the HashMap.

Step 4

If found and the index differs:

Code
return true

Step 5

After checking all words:

Code
return false

Example Walkthrough

Input

Code
["abc","cba"]

HashMap

Code
abc → 0
cba → 1

Processing

Code
word = abc

Split:

Code
abc | ""

Right side:

Code
""

is a palindrome.

Reverse of left:

Code
cba

exists.

Different index:

Code
1 ≠ 0

Return:

Code
true

Java Solution

Java
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

Code
["abc","cba"]

HashMap

Code
abc → 0
cba → 1

Processing

Code
abc

Split:

Code
abc | ""

Right:

Code
""

Palindrome:

Code
Yes

Reverse of left:

Code
cba

Found in map:

Code
Index = 1

Different from current index:

Code
1 != 0

Return:

Code
true

Complexity Analysis

Let:

Code
n = number of strings
l = maximum string length

Time Complexity

For every word:

Code
l splits

For each split:

Code
Palindrome check = O(l)

Total:

Code
O(n × l²)

Space Complexity

HashMap stores all strings:

Code
O(n × l)

Additional reverse strings and substrings:

Code
O(n × l²)

which matches the expected complexity.

Why This Solution Is Optimal

The brute-force solution compares every pair:

Code
O(n²)

which is impractical for:

Code
n = 20000

Using:

reduces the complexity to:

Code
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:

Code
Time Complexity: O(n × l²)
Space Complexity: O(n × l²)

making it suitable for large inputs and coding interviews.