Skip to main content

336 - Palindrome Pairs

Difficulty: Hard | Pattern: Hash Map + String | Company tags: Airbnb, Google, Uber

Problem Statement​

You are given a 0-indexed array of unique strings words.

A palindrome pair is a pair of integers (i, j) such that:

  • 0 <= i, j < words.length
  • i != j
  • words[i] + words[j] (the concatenation) is a palindrome.

Return an array of all the palindrome pairs of words.

Example 1:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]

Example 2:

Input: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]

Approach: Hash Map — O(n × k²)​

Key insight: For each word w at index i, we want to find another word that makes w + other or other + w a palindrome. We can use a hash map from word → index to look up candidates.

For word w, consider all ways to split it: prefix = w[:j] and suffix = w[j:].

  1. If suffix is a palindrome and reverse(prefix) exists in the map → [i, map[reverse(prefix)]]
  2. If prefix is a palindrome and reverse(suffix) exists in the map → [map[reverse(suffix)], i]
def palindromePairs(words: list[str]) -> list[list[int]]:
    word_map = {word: i for i, word in enumerate(words)}
    result = []
    
    def is_palindrome(s):
        return s == s[::-1]
    
    for i, word in enumerate(words):
        for j in range(len(word) + 1):
            prefix = word[:j]
            suffix = word[j:]
            
            # Case 1: suffix is palindrome, find reversed prefix
            if is_palindrome(suffix):
                rev_prefix = prefix[::-1]
                if rev_prefix in word_map and word_map[rev_prefix] != i:
                    result.append([i, word_map[rev_prefix]])
            
            # Case 2: prefix is palindrome, find reversed suffix
            # Avoid duplicate when j == len(word) (handled by case 1 with j==0)
            if j != len(word) and is_palindrome(prefix):
                rev_suffix = suffix[::-1]
                if rev_suffix in word_map and word_map[rev_suffix] != i:
                    result.append([word_map[rev_suffix], i])
    
    return result

Example Trace​

words = ["abcd","dcba","lls","s","sssll"], word_map: abcd→0, dcba→1, lls→2, s→3, sssll→4

For word = "lls" (i=2):

  • j=0: prefix="", suffix="lls" — is "lls" palindrome? No
  • j=1: prefix="l", suffix="ls" — is "ls" palindrome? No; is "l" palindrome? Yes, rev_suffix="sl" not in map
  • j=2: prefix="ll", suffix="s" — is "s" palindrome? Yes, rev_prefix="ll" not in map; is "ll" palindrome? Yes, rev_suffix="s" in map → append [3, 2]
  • j=3: prefix="lls", suffix="" — is "" palindrome? Yes, rev_prefix="sll" not in map

For word = "s" (i=3):

  • j=2: prefix="s", suffix="" — is "" palindrome? Yes; rev_prefix="s" in map but == i? No, wait word_map["s"]=3=i, skip
  • j=0: prefix="", suffix="s" — is "s" palindrome? Yes, rev_prefix="" not in map
  • j=1: prefix="s", suffix="" — already handled

Eventually produces pairs [3,2] and [2,4].

Edge Cases​

  • Empty string in words: "" + any palindrome = that palindrome → generates many pairs
  • Single character words: each is a palindrome; any reversed self-pair works
  • Duplicate check with word_map[rev] != i avoids using a word with itself

Complexity​

  • Time: O(n × k²) — for each of n words, up to k+1 splits, each palindrome check is O(k)
  • Space: O(n × k) — hash map storage

This is one of the more complex string problems — the key is seeing that we only need to check O(k) splits per word, not O(n) pairs.