Scale Engineer

Palindrome Pairs

Hard
#0323Time: O(N * K^2), where N is the number of words and K is the maximum length. For each of the N words, we iterate through K+1 split points. Inside the loop, substring creation, reversal, and palindrome checking can take up to O(K) time.Space: O(N * K), for storing the words in the HashMap.3 companies
Data structures
ArrayHash TableStringTrie
Companies
AirbnbWixYandex

Prompt

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, and
  • words[i] + words[j] (the concatenation of the two strings) is a palindrome.

Return an array of all the palindrome pairs of words.

You must write an algorithm with O(sum of words[i].length) runtime complexity.

 

Example 1:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

Example 2:

Input: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]

Example 3:

Input: words = ["a",""]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["a","a"]

 

Constraints:

  • 1 <= words.length <= 5000
  • 0 <= words[i].length <= 300
  • words[i] consists of lowercase English letters.

Approaches

4 approaches with complexity analysis and trade-offs.

We can optimize the brute-force approach by avoiding the inner loop that iterates through all other words. Instead, for each word w1, we can deduce what its partner word w2 must look like. If w1 + w2 is a palindrome, w2 must be related to the reverse of w1. We can pre-process the words into a HashMap for quick lookups.

There are three main scenarios for a pair (w1, w2):

  1. len(w1) == len(w2): w2 must be the reverse of w1.
  2. len(w1) > len(w2): w1 must be of the form P + S, where S is the reverse of w2 and P is a palindrome.
  3. len(w1) < len(w2): w2 must be of the form S + P, where S is the reverse of w1 and P is a palindrome.

We can iterate through each word and all its possible splits into a prefix and a suffix. If one part is a palindrome, we look for the reverse of the other part in the map.

Algorithm

  • Create a HashMap to store each word and its index. This allows for O(1) average time lookups.
  • Handle the edge case of an empty string. If "" exists in words, find its index. Then, iterate through all other words; if a word is a palindrome, it can form a pair with the empty string in both orders.
  • Iterate through each word w at index i in the words array.
  • For each word w, iterate through all possible split points j from 0 to w.length().
  • Split w into prefix = w.substring(0, j) and suffix = w.substring(j).
  • Case 1: Check if the prefix is a palindrome. If it is, reverse the suffix to get reversedSuffix. Look for reversedSuffix in the HashMap. If it exists at an index k different from i, then (k, i) is a palindrome pair (words[k] + words[i] forms a palindrome).
  • Case 2: Check if the suffix is a palindrome. If it is, reverse the prefix to get reversedPrefix. Look for reversedPrefix in the HashMap. If it exists at an index k different from i, then (i, k) is a palindrome pair. Note: When j=0, the prefix is empty, and this case becomes checking for the reverse of the whole word. To avoid duplicates when the suffix is empty (j = w.length()), we can add a condition suffix.length() > 0 or use a Set for the results.

Walkthrough

This approach improves upon brute force by intelligently searching for the second word in a pair. By pre-populating a HashMap with all words and their indices, we can quickly check for the existence of a required word (e.g., the reverse of a suffix). The main logic involves iterating through each word and, for each word, iterating through all possible split points. This creates a prefix and a suffix. We check if either part is a palindrome. If the prefix is a palindrome, we need a word that is the reverse of the suffix to place before our current word. If the suffix is a palindrome, we need a word that is the reverse of the prefix to place after our current word.

class Solution {    public List<List<Integer>> palindromePairs(String[] words) {        List<List<Integer>> result = new ArrayList<>();        Map<String, Integer> map = new HashMap<>();        for (int i = 0; i < words.length; i++) {            map.put(words[i], i);        }         for (int i = 0; i < words.length; i++) {            String word = words[i];            for (int j = 0; j <= word.length(); j++) {                String prefix = word.substring(0, j);                String suffix = word.substring(j);                 // Case 1: prefix is a palindrome, look for reversed suffix                if (isPalindrome(prefix)) {                    String reversedSuffix = new StringBuilder(suffix).reverse().toString();                    if (map.containsKey(reversedSuffix) && map.get(reversedSuffix) != i) {                        result.add(Arrays.asList(map.get(reversedSuffix), i));                    }                }                 // Case 2: suffix is a palindrome, look for reversed prefix                // suffix.length() != 0 to avoid duplicates when word is a palindrome                // (e.g. "aba", prefix="aba", suffix=""). This is handled by Case 1 when j=0.                if (isPalindrome(suffix) && suffix.length() != 0) {                    String reversedPrefix = new StringBuilder(prefix).reverse().toString();                    if (map.containsKey(reversedPrefix) && map.get(reversedPrefix) != i) {                        result.add(Arrays.asList(i, map.get(reversedPrefix)));                    }                }            }        }        return result;    }     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;            }        }        return true;    }}

Complexity

Time

O(N * K^2), where N is the number of words and K is the maximum length. For each of the N words, we iterate through K+1 split points. Inside the loop, substring creation, reversal, and palindrome checking can take up to O(K) time.

Space

O(N * K), for storing the words in the HashMap.

Trade-offs

Pros

  • Significantly faster than the brute-force approach for N > K.

  • Avoids the O(N^2) pair iteration.

Cons

  • The time complexity of O(N * K^2) might still be too slow for the given constraints.

  • Requires careful handling of edge cases like empty strings and duplicate pairs.

Solutions

using System.Collections.Generic ; using System.Linq ; public class Solution { public IList < IList < int >> PalindromePairs ( string [] words ) { var results = new List < IList < int >>(); var reverseDict = words . Select (( w , i ) => new { Word = w , Index = i }). ToDictionary ( w => new string ( w . Word . Reverse (). ToArray ()), w => w . Index ); for ( var i = 0 ; i < words . Length ; ++ i ) { var word = words [ i ]; for ( var j = 0 ; j <= word . Length ; ++ j ) { if ( j > 0 && IsPalindrome ( word , 0 , j - 1 )) { var suffix = word . Substring ( j ); int pairIndex ; if ( reverseDict . TryGetValue ( suffix , out pairIndex ) && i != pairIndex ) { results . Add ( new [] { pairIndex , i }); } } if ( IsPalindrome ( word , j , word . Length - 1 )) { var prefix = word . Substring ( 0 , j ); int pairIndex ; if ( reverseDict . TryGetValue ( prefix , out pairIndex ) && i != pairIndex ) { results . Add ( new [] { i , pairIndex }); } } } } return results ; } private bool IsPalindrome ( string word , int startIndex , int endIndex ) { var i = startIndex ; var j = endIndex ; while ( i < j ) { if ( word [ i ] != word [ j ]) return false ; ++ i ; -- j ; } return true ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem