Palindrome Pairs in an Array of Strings – Java Solution with HashMap

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:

Check every pair (i, j).
Concatenate strings.
Verify whether the result is a palindrome.

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:

Left Part
Right Part

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:

HashMap for reverse lookup
Palindrome prefix/suffix checking

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:

String manipulation
Hashing
Palindrome checking
Prefix and suffix decomposition

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.