Palindrome Pairs

Palindrome Pairs

What is this problem about?

The Palindrome Pairs problem gives you a list of unique words and asks you to find all index pairs (i, j) where the concatenation words[i] + words[j] forms a palindrome. This hard coding problem uses a hash map to efficiently check complements for each word split. The array, hash table, trie, and string interview pattern is the core.

Why is this asked in interviews?

Goldman Sachs, Meta, Yahoo, Amazon, Airbnb, and Google ask this because the naive O(n²k) approach (check all pairs) is too slow for large inputs. The efficient solution processes each word and checks whether valid palindrome-forming complements exist in the hash map, achieving O(nk²) time.

Algorithmic pattern used

Hash map with word splits. Build a hash map from word to index. For each word w at index i: split at every position j (0..len(w)): check w[0..j-1] and w[j..]. If w[j..] is a palindrome and reverse(w[0..j-1]) is in the map (at index k ≠ i): add pair (i, k). Similarly, if w[0..j-1] is a palindrome and reverse(w[j..]) is in the map: add pair (k, i). Handle empty string cases.

Example explanation

words=["abcd","dcba","lls","s","sssll"]. Word map: {abcd:0,dcba:1,lls:2,s:3,sssll:4}.

• "abcd": split "", "abcd" → "" is palindrome, reverse("abcd")="dcba" in map → pair (0,1). Split "abcd","" → "abcd" palindrome? No. Split "a","bcd" → "bcd" palindrome? No.
• More splits and checks yield: (1,0),(3,2),(2,4),(4,2) etc.

Common mistakes candidates make

• O(n²) brute force (TLE for large inputs).
• Duplicate pairs from symmetric splits.
• Not handling empty strings in the map.
• Not checking i ≠ k to avoid self-pairing.

Interview preparation tip

Palindrome Pairs is a complex string problem requiring careful case analysis. The key insight: for w+v to be a palindrome, split w at each position and check if the remaining part is (a) itself a palindrome and (b) its reverse is in the map. Draw the three cases (v is reverse of w, prefix of w is palindrome + reverse(suffix) in map, suffix is palindrome + reverse(prefix) in map) on paper first. Practice building palindrome-checking functions efficiently before this problem.