Vultr DocsLatest Content

Palindrome Pairs

Updated on 03 July, 2025
Palindrome Pairs header image

Problem Statement

The task involves processing a given zero-indexed array of unique strings named words. The goal is to identify all "palindrome pairs" in this array. A "palindrome pair" is defined as a pair of indices (i, j) satisfying the conditions:

  • Both indices must be within the range of the array,
  • The indices must not be identical,
  • The concatenation of the strings at these indices (words[i] + words[j]) should form a palindrome (a word that reads the same backward as forward).

The desired output is an array listing all such palindrome pairs. The provided solution is expected to operate within a time complexity proportional to the sum of the lengths of the strings in words, specifically O(sum of words[i].length).

Examples

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.

Approach and Intuition

  1. Identifying Palindromes: To determine if a concatenated string forms a palindrome, you can simply check if the string equals its reverse.
  2. Palindrome Pair Identification:
    • Iterate through the array words.
    • For each word, generate all possible prefixes and suffixes, including the word itself.
    • Check if these prefixes or suffixes themselves are palindromic. If a prefix is palindromic, then find if there exists a reverse of a remaining suffix in the array words as a full word.
    • Apply similar logic for the suffixes.
  3. Efficient Search with Hashtable:
    • Use a hashtable to store the words for quick lookup in O(1) average time complexity. The keys would be the words in the array, and the values would be their corresponding indices.
    • This allows checking for corresponding pair complements efficiently as you process each word and its potential palindrome forming prefixes and suffixes.
  4. Handling the Empty String Special Case:
    • An empty string "" when paired with any palindrome word forms a palindrome pair. Specifically, if "" exists in the list, then for any word which is a palindrome by itself, (index of "", index of palindrome word) is a valid pair.

Using these strategies, a program can be implemented which explores all potential palindrome pairs with the required time efficiency by making use of string manipulations and hashtable data structures.

Solutions

  • Java
java 
class TrieNode {
    // Note that -1 signifies no word ends here
    public int endOfWord = -1;
    public Map<Character, TrieNode> children = new HashMap<>();
    public List<Integer> palindromicSuffixIndices = new ArrayList<>();
}
    
class Solution {
    
    // Check if substring from index i to end of string s is a palindrome
    public boolean isSuffixPalindrome(String s, int i) {
        int left = i;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
    
    public List<List<Integer>> findPalindromePairs(String[] words) {
    
        TrieNode root = new TrieNode();
    
        // Construct Trie with reversed words
        for (int id = 0; id < words.length; id++) {
            String word = words[id];
            String reversed = new StringBuilder(word).reverse().toString();
            TrieNode node = root;
            for (int j = 0; j < word.length(); j++) {
                if (isSuffixPalindrome(reversed, j)) {
                    node.palindromicSuffixIndices.add(id);
                }
                char ch = reversed.charAt(j);
                if (!node.children.containsKey(ch)) {
                    node.children.put(ch, new TrieNode());
                }
                node = node.children.get(ch);
            }
            node.endOfWord = id;
        }
    
        // Search for palindrome pairs
        List<List<Integer>> result = new ArrayList<>();
        for (int id = 0; id < words.length; id++) {
            String word = words[id];
            TrieNode node = root;
            for (int j = 0; j < word.length(); j++) {
                // Case 3
                if (node.endOfWord != -1 && isSuffixPalindrome(word, j)) {
                    result.add(Arrays.asList(id, node.endOfWord));
                }
                char ch = word.charAt(j);
                node = node.children.get(ch);
                if (node == null) break;
            }
            if (node == null) continue;
            // Case 1
            if (node.endOfWord != -1 && node.endOfWord != id) {
                result.add(Arrays.asList(id, node.endOfWord));
            }
            // Case 2
            for (int otherId : node.palindromicSuffixIndices) {
                result.add(Arrays.asList(id, otherId));
            }
        }
    
        return result;
    }
}

The provided Java solution solves the problem of finding all unique pairs of words that, when combined, form a palindrome. The approach leverages a Trie data structure tailored for this specific problem, where each Trie node contains:

  • A hashmap for child nodes to maintain branching for character paths.
  • A termination indicator showing if any word ends at that node and it's respective index in the input list.
  • A list of indices where the corresponding suffixes starting from a certain position in the word are palindromic.

Here is a step-by-step breakdown of the solution approach:

  1. Trie Construction: The solution first constructs a Trie where each inserted word is reversed. This reversal helps in easy detection of potential palindromic concatenations at later stages. During insertion, the algorithm also examines if the remaining suffix of the reversed word forms a palindrome and annotates accordingly in palindromicSuffixIndices.

  2. Palindrome Pair Detection: For each word in the input list, the solution attempts to traverse down the Trie based on the characters of the word. Throughout the traversal:

    • Checks if the current path terminated forms a palindrome with the prefix of another word (using recorded indices at Trie nodes).
    • Continues to match characters of the word against nodes in the Trie.
    • Additionally, identifies complete word matches and suffix/prefix palindromic conditions leveraging the palindromicSuffixIndices and endOfWord markers.

  3. Result Compilation: Every time the above conditions are satisfied (complete match or valid palindromic suffix/prefix scenarios are encountered), the pair of indices is added to the result list indicating a palindromic pair.

The Trie-based algorithm provides an efficient method to check for palindromic concatenations as opposed to a brute-force approach which would involve checking all possible pair combinations. This optimization is particularly important given the potentially large size of input words array. The critical aspect of this solution is handling the palindrome checks both at Trie construction and during the palindrome search phase, ensuring only valid pairs are collected.

Comments

No comments yet.