Palindrome Pairs

Intuition

A concatenation s + t is a palindrome when one side can be mirrored by the other, plus a center piece that is itself palindrome. So for each word, try every split into prefix and suffix. If prefix is palindrome, we need a word equal to reverse(suffix); if suffix is palindrome, we need reverse(prefix). Hash-map lookups make these checks fast.

Algorithm

1Build a hash map from reversed word to its index.
2For each word s at index i, iterate split position j from 0 to s.length().
3Let s1 = s[0..j-1], s2 = s[j..end].
4If prefix s1 is palindrome and map contains s2 at index != i, return true.
5If suffix s2 is palindrome and map contains s1 at index != i, return true.
6If no split works for any word, return false.

Example Walkthrough

Input: arr = ["abcd", "dcba", "lls", "s", "sssll"]

1.Store reversed words: "dcba"→0, "abcd"→1, "sll"→2, "s"→3, "llsss"→4.
2.For word "abcd" (i=0), split j=0 gives s1="" (palindrome), s2="abcd".
3.Map contains "abcd" at index 1, and 1 != 0, so pair exists.
4.Hence "abcd" + "dcba" is a palindrome.

Output: true

Common Pitfalls

•Always enforce i != matchedIndex; otherwise a word may incorrectly pair with itself.
•Handle empty prefix/suffix splits (j = 0 or j = len); they are valid and often necessary.
•When duplicate words are possible, storing only one index can miss combinations; a list of indices is safer in that variant.

Palindrome Pairs.java

Java


import java.util.*;

// Approach: Store each word's reversed form in a hash map for O(1) partner lookups.
// For every split of a word into prefix/suffix, if one part is palindrome,
// check whether the reverse of the other part exists as a different index.
// If such a match exists for any split, a palindrome pair exists.
// Time: O(n * L^2) Space: O(n * L)

class Solution {

    public boolean palindromePair(String[] arr) {
        HashMap<String, Integer> hm = new HashMap<>();
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder(arr[i]);
            hm.put(sb.reverse().toString(), i);
        }

        for (int i = 0; i < n; i++) {
            String s = arr[i];
            int l = s.length();
            for (int j = 0; j <= l; j++) {
                String s1 = s.substring(0, j);
                String s2 = s.substring(j, l);
                if (pal(s, j) && hm.containsKey(s2) && i != hm.get(s2)) {
                    return true;
                }
                if (pal(s2, l - j) && hm.containsKey(s1) && i != hm.get(s1)) {
                    return true;
                }
            }
        }

        return false;
    }

    static boolean pal(String s, int n) {
        if (n == 0 || n == 1) {
            return true;
        }
        
        int i = 0, j = n - 1;
        while (i <= j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }

        return true;
    }
}

Was this solution helpful?