Palindrome Pairs

🎯

Palindrome Pairs

hardMIXEDGoogleAmazonAirbnb

Imagine a search engine that suggests pairs of words which, when combined, form palindromes - a fun feature for word games or linguistic puzzles.

💡 This problem involves checking pairs of words to see if their concatenation forms a palindrome. Beginners often struggle because the naive approach is very slow, and the problem requires clever use of data structures like tries or hash maps combined with palindrome checks to optimize.

📋

Problem Statement

Given a list of unique words, find all pairs of distinct indices (i, j) such that the concatenation of words[i] + words[j] is a palindrome. Return all such pairs as a list of lists.

1 ≤ n ≤ 10^5 (number of words)1 ≤ length of each word ≤ 300All words consist of lowercase English lettersWords are unique

💡

Example

Input["abcd","dcba","lls","s","sssll"]

Output01103224

Pairs: 'abcd' + 'dcba' = 'abcddcba' palindrome, 'dcba' + 'abcd' palindrome, 's' + 'lls' palindrome, 'lls' + 'sssll' palindrome.

• Empty string present → pairs with any palindrome word
• Single character words → always palindrome pairs with themselves reversed
• Words that are already palindromes → can form pairs with empty string
• No palindrome pairs → return empty list

⚠️

Common Mistakes

Not checking empty string cases

Misses pairs involving empty string which can pair with any palindrome word

✅ Explicitly handle empty string as a special case or ensure palindrome checks cover empty substrings

Pairing word with itself

Incorrect pairs like (i, i) appear in output

✅ Always check indices are distinct before adding pairs

Double counting pairs

Pairs appear twice in output, e.g., both (i,j) and (j,i)

✅ Use conditions to avoid duplicates or use sets to store results

Inefficient palindrome checks inside loops

Code runs slowly or times out on large inputs

✅ Optimize palindrome checks by caching results or using two-pointer checks efficiently

Incorrect substring indices when splitting words

Wrong pairs or runtime errors due to off-by-one errors

✅ Carefully handle substring boundaries and test with small examples

🧠

Brute Force (Nested Loops with Palindrome Check)

💡 This approach exists to build foundational understanding by directly checking all pairs. It is simple but inefficient, highlighting why optimization is necessary.

Intuition

Check every possible pair of words by concatenating them and verifying if the result is a palindrome.

Algorithm

1. Iterate over all pairs (i, j) where i != j
2. Concatenate words[i] + words[j]
3. Check if the concatenated string is a palindrome
4. If yes, add the pair (i, j) to the result list

💡 The nested loops and palindrome checks are straightforward but can be overwhelming due to the large input size and string operations.

</>

Code

def palindromePairs(words):
    def is_palindrome(check):
        return check == check[::-1]

    res = []
    n = len(words)
    for i in range(n):
        for j in range(n):
            if i != j:
                combined = words[i] + words[j]
                if is_palindrome(combined):
                    res.append([i, j])
    return res

# Example usage
if __name__ == '__main__':
    words = ["abcd","dcba","lls","s","sssll"]
    print(palindromePairs(words))

Line Notes

def is_palindrome(check):Defines a helper to check palindrome property for clarity and reuse

return check == check[::-1]Checks palindrome by comparing string to its reverse

for i in range(n):Outer loop picks the first word index

for j in range(n):Inner loop picks the second word index to pair with first

if i != j:Avoid pairing a word with itself

combined = words[i] + words[j]Concatenate the two words to check palindrome

if is_palindrome(combined):Check if concatenation forms a palindrome

res.append([i, j])Add valid palindrome pair indices to result

import java.util.*;

public class PalindromePairs {
    public static boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }

    public static List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> res = new ArrayList<>();
        int n = words.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    String combined = words[i] + words[j];
                    if (isPalindrome(combined)) {
                        res.add(Arrays.asList(i, j));
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String[] words = {"abcd","dcba","lls","s","sssll"};
        System.out.println(palindromePairs(words));
    }
}

Line Notes

public static boolean isPalindrome(String s) {Helper method to check palindrome by two-pointer technique

while (left < right) {Two pointers move inward to compare characters

if (s.charAt(left) != s.charAt(right)) return false;Early exit if mismatch found

for (int i = 0; i < n; i++) {Outer loop selects first word

for (int j = 0; j < n; j++) {Inner loop selects second word

if (i != j) {Avoid pairing word with itself

String combined = words[i] + words[j];Concatenate words to check palindrome

if (isPalindrome(combined)) {Check palindrome condition

res.add(Arrays.asList(i, j));Add valid pair to result list

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool isPalindrome(const string& s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

vector<vector<int>> palindromePairs(vector<string>& words) {
    vector<vector<int>> res;
    int n = words.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) {
                string combined = words[i] + words[j];
                if (isPalindrome(combined)) {
                    res.push_back({i, j});
                }
            }
        }
    }
    return res;
}

int main() {
    vector<string> words = {"abcd","dcba","lls","s","sssll"};
    vector<vector<int>> result = palindromePairs(words);
    for (auto& pair : result) {
        cout << "[" << pair[0] << "," << pair[1] << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

bool isPalindrome(const string& s) {Helper function to check palindrome using two pointers

while (left < right) {Compare characters from both ends moving inward

if (s[left] != s[right]) return false;Return false immediately if mismatch found

for (int i = 0; i < n; i++) {Outer loop picks first word index

for (int j = 0; j < n; j++) {Inner loop picks second word index

if (i != j) {Skip pairing word with itself

string combined = words[i] + words[j];Concatenate two words

if (isPalindrome(combined)) {Check if concatenation is palindrome

res.push_back({i, j});Add valid pair to results

function isPalindrome(s) {
    let left = 0, right = s.length - 1;
    while (left < right) {
        if (s[left] !== s[right]) return false;
        left++;
        right--;
    }
    return true;
}

function palindromePairs(words) {
    const res = [];
    const n = words.length;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (i !== j) {
                const combined = words[i] + words[j];
                if (isPalindrome(combined)) {
                    res.push([i, j]);
                }
            }
        }
    }
    return res;
}

// Example usage
const words = ["abcd","dcba","lls","s","sssll"];
console.log(palindromePairs(words));

Line Notes

function isPalindrome(s) {Helper function to check palindrome with two pointers

while (left < right) {Compare characters from both ends

if (s[left] !== s[right]) return false;Return false on mismatch

for (let i = 0; i < n; i++) {Outer loop selects first word

for (let j = 0; j < n; j++) {Inner loop selects second word

if (i !== j) {Avoid pairing word with itself

const combined = words[i] + words[j];Concatenate words to check palindrome

if (isPalindrome(combined)) {Check palindrome condition

res.push([i, j]);Add valid pair to result array

⏱

Complexity

TimeO(n^2 * k) where n is number of words and k is max word length

SpaceO(n) for output storage

We check all pairs (n^2) and for each pair, palindrome check takes O(k) due to string concatenation and palindrome verification.

💡 For n=1000 and k=10, this means about 1 million palindrome checks, which is slow but manageable for small inputs.

Interview Verdict: TLE for large inputs

This approach is too slow for large inputs but is a good starting point to understand the problem and correctness.

🧠

Hash Map + Palindrome Prefix/Suffix Check

💡 This approach improves efficiency by using a hash map to find reversed words quickly and checking palindrome prefixes and suffixes to reduce unnecessary checks.

Intuition

Store all words in a hash map keyed by word to index. For each word, split it into prefix and suffix, check if one part is palindrome and if the reversed other part exists in the map.

Algorithm

1. Create a hash map from word to index
2. For each word, iterate over all splits into prefix and suffix
3. If prefix is palindrome, check if reversed suffix exists in map and is different word
4. If suffix is palindrome, check if reversed prefix exists in map and is different word
5. Add all valid pairs to result

💡 The key insight is splitting words and leveraging palindrome checks on parts to find pairs efficiently.

</>

Code

def palindromePairs(words):
    def is_palindrome(check):
        return check == check[::-1]

    wordict = {w: i for i, w in enumerate(words)}
    res = []
    for i, word in enumerate(words):
        for j in range(len(word)+1):
            prefix = word[:j]
            suffix = word[j:]
            if is_palindrome(prefix):
                back = suffix[::-1]
                if back in wordict and wordict[back] != i:
                    res.append([wordict[back], i])
            if j != len(word) and is_palindrome(suffix):
                front = prefix[::-1]
                if front in wordict and wordict[front] != i:
                    res.append([i, wordict[front]])
    return res

# Example usage
if __name__ == '__main__':
    words = ["abcd","dcba","lls","s","sssll"]
    print(palindromePairs(words))

Line Notes

wordict = {w: i for i, w in enumerate(words)}Maps each word to its index for O(1) lookups

for i, word in enumerate(words):Iterate over each word with index

for j in range(len(word)+1):Split word into prefix and suffix at every position

if is_palindrome(prefix):Check if prefix is palindrome to consider suffix reversed

back = suffix[::-1]Reverse suffix to find matching word

if back in wordict and wordict[back] != i:Check existence and avoid pairing word with itself

res.append([wordict[back], i])Add pair where reversed suffix precedes current word

if j != len(word) and is_palindrome(suffix):Check suffix palindrome for reversed prefix pairing

front = prefix[::-1]Reverse prefix to find matching word

if front in wordict and wordict[front] != i:Check existence and avoid self pairing

res.append([i, wordict[front]])Add pair where current word precedes reversed prefix

import java.util.*;

public class PalindromePairs {
    public static boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }

    public static List<List<Integer>> palindromePairs(String[] words) {
        Map<String, Integer> wordict = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            wordict.put(words[i], i);
        }
        List<List<Integer>> res = new ArrayList<>();
        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);
                if (isPalindrome(prefix)) {
                    String back = new StringBuilder(suffix).reverse().toString();
                    if (wordict.containsKey(back) && wordict.get(back) != i) {
                        res.add(Arrays.asList(wordict.get(back), i));
                    }
                }
                if (j != word.length() && isPalindrome(suffix)) {
                    String front = new StringBuilder(prefix).reverse().toString();
                    if (wordict.containsKey(front) && wordict.get(front) != i) {
                        res.add(Arrays.asList(i, wordict.get(front)));
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String[] words = {"abcd","dcba","lls","s","sssll"};
        System.out.println(palindromePairs(words));
    }
}

Line Notes

Map<String, Integer> wordict = new HashMap<>();Hash map for quick word to index lookup

wordict.put(words[i], i);Populate map with word and its index

for (int i = 0; i < words.length; i++) {Iterate over each word

for (int j = 0; j <= word.length(); j++) {Split word into prefix and suffix

if (isPalindrome(prefix)) {Check if prefix is palindrome

String back = new StringBuilder(suffix).reverse().toString();Reverse suffix to find matching word

if (wordict.containsKey(back) && wordict.get(back) != i) {Check existence and avoid self pairing

res.add(Arrays.asList(wordict.get(back), i));Add pair with reversed suffix before current word

if (j != word.length() && isPalindrome(suffix)) {Check suffix palindrome for reversed prefix

String front = new StringBuilder(prefix).reverse().toString();Reverse prefix

if (wordict.containsKey(front) && wordict.get(front) != i) {Check existence and avoid self pairing

res.add(Arrays.asList(i, wordict.get(front)));Add pair with current word before reversed prefix

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

bool isPalindrome(const string& s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

vector<vector<int>> palindromePairs(vector<string>& words) {
    unordered_map<string, int> wordict;
    for (int i = 0; i < words.size(); i++) {
        wordict[words[i]] = i;
    }
    vector<vector<int>> res;
    for (int i = 0; i < words.size(); i++) {
        string word = words[i];
        for (int j = 0; j <= word.size(); j++) {
            string prefix = word.substr(0, j);
            string suffix = word.substr(j);
            if (isPalindrome(prefix)) {
                string back = suffix;
                reverse(back.begin(), back.end());
                if (wordict.count(back) && wordict[back] != i) {
                    res.push_back({wordict[back], i});
                }
            }
            if (j != word.size() && isPalindrome(suffix)) {
                string front = prefix;
                reverse(front.begin(), front.end());
                if (wordict.count(front) && wordict[front] != i) {
                    res.push_back({i, wordict[front]});
                }
            }
        }
    }
    return res;
}

int main() {
    vector<string> words = {"abcd","dcba","lls","s","sssll"};
    vector<vector<int>> result = palindromePairs(words);
    for (auto& pair : result) {
        cout << "[" << pair[0] << "," << pair[1] << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

unordered_map<string, int> wordict;Hash map for word to index lookup

wordict[words[i]] = i;Store each word with its index

for (int i = 0; i < words.size(); i++) {Iterate over words

for (int j = 0; j <= word.size(); j++) {Split word into prefix and suffix

if (isPalindrome(prefix)) {Check prefix palindrome

reverse(back.begin(), back.end());Reverse suffix to find matching word

if (wordict.count(back) && wordict[back] != i) {Check existence and avoid self pairing

res.push_back({wordict[back], i});Add pair with reversed suffix before current word

if (j != word.size() && isPalindrome(suffix)) {Check suffix palindrome

reverse(front.begin(), front.end());Reverse prefix

if (wordict.count(front) && wordict[front] != i) {Check existence and avoid self pairing

res.push_back({i, wordict[front]});Add pair with current word before reversed prefix

function isPalindrome(s) {
    let left = 0, right = s.length - 1;
    while (left < right) {
        if (s[left] !== s[right]) return false;
        left++;
        right--;
    }
    return true;
}

function palindromePairs(words) {
    const wordict = new Map();
    words.forEach((w, i) => wordict.set(w, i));
    const res = [];
    for (let i = 0; i < words.length; i++) {
        const word = words[i];
        for (let j = 0; j <= word.length; j++) {
            const prefix = word.substring(0, j);
            const suffix = word.substring(j);
            if (isPalindrome(prefix)) {
                const back = suffix.split('').reverse().join('');
                if (wordict.has(back) && wordict.get(back) !== i) {
                    res.push([wordict.get(back), i]);
                }
            }
            if (j !== word.length && isPalindrome(suffix)) {
                const front = prefix.split('').reverse().join('');
                if (wordict.has(front) && wordict.get(front) !== i) {
                    res.push([i, wordict.get(front)]);
                }
            }
        }
    }
    return res;
}

// Example usage
const words = ["abcd","dcba","lls","s","sssll"];
console.log(palindromePairs(words));

Line Notes

const wordict = new Map();Map words to indices for O(1) lookup

words.forEach((w, i) => wordict.set(w, i));Populate map with word and index

for (let i = 0; i < words.length; i++) {Iterate over each word

for (let j = 0; j <= word.length; j++) {Split word into prefix and suffix

if (isPalindrome(prefix)) {Check if prefix is palindrome

const back = suffix.split('').reverse().join('');Reverse suffix to find matching word

if (wordict.has(back) && wordict.get(back) !== i) {Check existence and avoid self pairing

res.push([wordict.get(back), i]);Add pair with reversed suffix before current word

if (j !== word.length && isPalindrome(suffix)) {Check suffix palindrome

const front = prefix.split('').reverse().join('');Reverse prefix

if (wordict.has(front) && wordict.get(front) !== i) {Check existence and avoid self pairing

res.push([i, wordict.get(front)]);Add pair with current word before reversed prefix

⏱

Complexity

TimeO(n * k^2) where n is number of words and k is max word length

SpaceO(n * k) for hash map and output

For each word, we check all splits (k) and palindrome checks (k), total O(k^2) per word. Hash map lookups are O(1).

💡 For n=1000 and k=10, this is about 100,000 operations, much faster than brute force.

Interview Verdict: Accepted for large inputs

This approach is efficient enough for large inputs and is a common interview solution.

🧠

Trie-Based Solution with Palindrome Suffix Tracking

💡 This approach uses a trie to store reversed words and tracks palindrome suffixes to find pairs efficiently, demonstrating advanced data structure usage.

Intuition

Insert reversed words into a trie, storing indices of words whose suffixes form palindromes. For each word, traverse the trie to find matching prefixes and use stored palindrome suffix indices to find pairs.

Algorithm

1. Build a trie by inserting reversed words, storing indices and palindrome suffix info at nodes
2. For each word, traverse the trie matching characters
3. If at any point the remaining substring is palindrome, add pairs using stored indices
4. After traversal, add pairs from palindrome suffix indices stored at the current node

💡 The complexity lies in managing the trie and palindrome suffix lists, but it reduces redundant checks.

</>

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.index = -1
        self.palindrome_suffixes = []

def is_palindrome(word):
    return word == word[::-1]

def palindromePairs(words):
    root = TrieNode()

    def add_word(word, index):
        node = root
        for i, ch in enumerate(reversed(word)):
            if is_palindrome(word[:len(word)-i]):
                node.palindrome_suffixes.append(index)
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.index = index
        node.palindrome_suffixes.append(index)

    def search(word, index):
        res = []
        node = root
        for i, ch in enumerate(word):
            if node.index >= 0 and node.index != index and is_palindrome(word[i:]):
                res.append([index, node.index])
            if ch not in node.children:
                return res
            node = node.children[ch]
        for j in node.palindrome_suffixes:
            if j != index:
                res.append([index, j])
        return res

    for i, word in enumerate(words):
        add_word(word, i)

    result = []
    for i, word in enumerate(words):
        result.extend(search(word, i))
    return result

# Example usage
if __name__ == '__main__':
    words = ["abcd","dcba","lls","s","sssll"]
    print(palindromePairs(words))

Line Notes

class TrieNode:Defines trie node structure with children, index, and palindrome suffix list

def add_word(word, index):Inserts reversed word into trie, tracking palindrome suffixes

if is_palindrome(word[:len(word)-i]):Check if prefix of reversed word is palindrome to store suffix info

node.index = indexMark node as end of word with index

def search(word, index):Search trie for pairs matching current word

if node.index >= 0 and node.index != index and is_palindrome(word[i:]):Check if remaining substring is palindrome to add pair

for j in node.palindrome_suffixes:Add pairs from stored palindrome suffix indices

result.extend(search(word, i))Collect all pairs found for current word

import java.util.*;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    int index = -1;
    List<Integer> palindromeSuffixes = new ArrayList<>();
}

public class PalindromePairs {
    public static boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }

    TrieNode root = new TrieNode();

    public void addWord(String word, int index) {
        TrieNode node = root;
        for (int i = word.length() - 1; i >= 0; i--) {
            if (isPalindrome(word.substring(0, i + 1))) {
                node.palindromeSuffixes.add(index);
            }
            char ch = word.charAt(i);
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.index = index;
        node.palindromeSuffixes.add(index);
    }

    public List<List<Integer>> search(String word, int index) {
        List<List<Integer>> res = new ArrayList<>();
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            if (node.index >= 0 && node.index != index && isPalindrome(word.substring(i))) {
                res.add(Arrays.asList(index, node.index));
            }
            char ch = word.charAt(i);
            if (!node.children.containsKey(ch)) return res;
            node = node.children.get(ch);
        }
        for (int j : node.palindromeSuffixes) {
            if (j != index) res.add(Arrays.asList(index, j));
        }
        return res;
    }

    public List<List<Integer>> palindromePairs(String[] words) {
        for (int i = 0; i < words.length; i++) {
            addWord(words[i], i);
        }
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            result.addAll(search(words[i], i));
        }
        return result;
    }

    public static void main(String[] args) {
        PalindromePairs sol = new PalindromePairs();
        String[] words = {"abcd","dcba","lls","s","sssll"};
        System.out.println(sol.palindromePairs(words));
    }
}

Line Notes

class TrieNode {Trie node with children map, index, and palindrome suffix list

public void addWord(String word, int index) {Insert reversed word into trie with palindrome suffix tracking

if (isPalindrome(word.substring(0, i + 1))) {Check prefix palindrome to store suffix info

node.index = index;Mark end of word with index

public List<List<Integer>> search(String word, int index) {Search trie for palindrome pairs

if (node.index >= 0 && node.index != index && isPalindrome(word.substring(i))) {Check remaining substring palindrome to add pair

for (int j : node.palindromeSuffixes) {Add pairs from stored palindrome suffix indices

result.addAll(search(words[i], i));Collect all pairs for current word

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    int index = -1;
    vector<int> palindromeSuffixes;
};

bool isPalindrome(const string& s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

class Solution {
    TrieNode* root = new TrieNode();

    void addWord(const string& word, int index) {
        TrieNode* node = root;
        for (int i = word.size() - 1; i >= 0; i--) {
            if (isPalindrome(word.substr(0, i + 1))) {
                node->palindromeSuffixes.push_back(index);
            }
            char ch = word[i];
            if (!node->children.count(ch)) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->index = index;
        node->palindromeSuffixes.push_back(index);
    }

    vector<vector<int>> search(const string& word, int index) {
        vector<vector<int>> res;
        TrieNode* node = root;
        for (int i = 0; i < word.size(); i++) {
            if (node->index >= 0 && node->index != index && isPalindrome(word.substr(i))) {
                res.push_back({index, node->index});
            }
            char ch = word[i];
            if (!node->children.count(ch)) return res;
            node = node->children[ch];
        }
        for (int j : node->palindromeSuffixes) {
            if (j != index) res.push_back({index, j});
        }
        return res;
    }

public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        for (int i = 0; i < words.size(); i++) {
            addWord(words[i], i);
        }
        vector<vector<int>> result;
        for (int i = 0; i < words.size(); i++) {
            auto pairs = search(words[i], i);
            result.insert(result.end(), pairs.begin(), pairs.end());
        }
        return result;
    }
};

int main() {
    vector<string> words = {"abcd","dcba","lls","s","sssll"};
    Solution sol;
    vector<vector<int>> result = sol.palindromePairs(words);
    for (auto& pair : result) {
        cout << "[" << pair[0] << "," << pair[1] << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

struct TrieNode {Trie node with children map, index, and palindrome suffix vector

void addWord(const string& word, int index) {Insert reversed word with palindrome suffix tracking

if (isPalindrome(word.substr(0, i + 1))) {Check prefix palindrome to store suffix info

node->index = index;Mark end of word with index

vector<vector<int>> search(const string& word, int index) {Search trie for palindrome pairs

if (node->index >= 0 && node->index != index && isPalindrome(word.substr(i))) {Check remaining substring palindrome

for (int j : node->palindromeSuffixes) {Add pairs from stored palindrome suffix indices

result.insert(result.end(), pairs.begin(), pairs.end());Collect all pairs for current word

class TrieNode {
    constructor() {
        this.children = new Map();
        this.index = -1;
        this.palindromeSuffixes = [];
    }
}

function isPalindrome(s) {
    let left = 0, right = s.length - 1;
    while (left < right) {
        if (s[left] !== s[right]) return false;
        left++;
        right--;
    }
    return true;
}

class PalindromePairs {
    constructor() {
        this.root = new TrieNode();
    }

    addWord(word, index) {
        let node = this.root;
        for (let i = word.length - 1; i >= 0; i--) {
            if (isPalindrome(word.substring(0, i + 1))) {
                node.palindromeSuffixes.push(index);
            }
            const ch = word[i];
            if (!node.children.has(ch)) {
                node.children.set(ch, new TrieNode());
            }
            node = node.children.get(ch);
        }
        node.index = index;
        node.palindromeSuffixes.push(index);
    }

    search(word, index) {
        const res = [];
        let node = this.root;
        for (let i = 0; i < word.length; i++) {
            if (node.index >= 0 && node.index !== index && isPalindrome(word.substring(i))) {
                res.push([index, node.index]);
            }
            const ch = word[i];
            if (!node.children.has(ch)) return res;
            node = node.children.get(ch);
        }
        for (const j of node.palindromeSuffixes) {
            if (j !== index) res.push([index, j]);
        }
        return res;
    }

    palindromePairs(words) {
        for (let i = 0; i < words.length; i++) {
            this.addWord(words[i], i);
        }
        const result = [];
        for (let i = 0; i < words.length; i++) {
            result.push(...this.search(words[i], i));
        }
        return result;
    }
}

// Example usage
const words = ["abcd","dcba","lls","s","sssll"];
const sol = new PalindromePairs();
console.log(sol.palindromePairs(words));

Line Notes

class TrieNode {Trie node with children map, index, and palindrome suffix array

addWord(word, index) {Insert reversed word with palindrome suffix tracking

if (isPalindrome(word.substring(0, i + 1))) {Check prefix palindrome to store suffix info

node.index = index;Mark end of word with index

search(word, index) {Search trie for palindrome pairs

if (node.index >= 0 && node.index !== index && isPalindrome(word.substring(i))) {Check remaining substring palindrome

for (const j of node.palindromeSuffixes) {Add pairs from stored palindrome suffix indices

result.push(...this.search(words[i], i));Collect all pairs for current word

⏱

Complexity

TimeO(n * k^2) where n is number of words and k is max word length

SpaceO(n * k) for trie nodes and palindrome suffix lists

Building and searching trie involves checking palindrome substrings and traversing characters, each O(k^2) per word due to palindrome checks at each character.

💡 Though complex, this approach is efficient and scalable for large inputs with many words.

Interview Verdict: Accepted and optimal for large inputs

This approach demonstrates mastery of tries and palindrome properties, often expected in top-tier interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the hash map approach is usually the best balance of clarity and efficiency to implement quickly.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2 * k)	O(n)	No	N/A	Mention only - never code due to inefficiency
2. Hash Map + Palindrome Prefix/Suffix Check	O(n * k^2)	O(n * k)	No	Yes	Code this approach for best tradeoff
3. Trie-Based Solution	O(n * k^2)	O(n * k)	No	Yes	Mention or code if advanced trie knowledge is expected

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding each approach, and prepare to explain tradeoffs and optimizations clearly in interviews.

How to Present

Clarify problem constraints and examplesState brute force approach and its inefficiencyExplain hash map optimization with palindrome prefix/suffix checksDiscuss trie-based advanced solution if time permitsCode the hash map approach as it balances clarity and efficiencyTest with edge cases and explain complexity

Time Allocation

Clarify: 3min → Approach: 5min → Code: 15min → Test & Optimize: 7min. Total ~30min

What the Interviewer Tests

Ability to identify brute force, optimize using hashing and palindrome properties, and optionally implement advanced trie-based solution; also tests string manipulation and edge case handling.

Common Follow-ups

• How to handle duplicates or non-unique words → Use additional data structures or modify approach
• Can we optimize palindrome checks → Use caching or precompute palindrome substrings

💡 These follow-ups test deeper understanding of palindrome properties and handling real-world input variations.

🔍

Pattern Recognition

When to Use

1) Problem involves pairs of words or strings; 2) Palindrome property is central; 3) Need to optimize pair checking; 4) Use of reversed strings or prefix/suffix palindrome checks is possible.

Signature Phrases

concatenation forms a palindromefind all pairsreverse of substring

NOT This Pattern When

Problems that only check if a single string is palindrome or count palindromic substrings without pairing.

Similar Problems

Palindrome Partitioning - also involves palindrome substring checksLongest Palindromic Substring - focuses on palindrome detectionValid Palindrome - basic palindrome checking

Practice

1. You are given an array of integers and multiple queries. Each query provides a number x and a limit m. For each query, you must find the maximum XOR of x with any array element less than or equal to m. Which approach guarantees an optimal solution for large inputs?

easy

A. Sort the array and queries, then use a bitwise trie to insert elements up to the query limit and find max XOR.

B. Use dynamic programming to store XOR results for all subarrays and answer queries in O(1).

C. Use a brute force nested loop checking all elements for each query.

D. Apply a greedy approach by always choosing the element with the highest value less than or equal to m.

Solution

1. Step 1: Understand problem constraints

   Brute force is too slow for large inputs; DP for subarrays doesn't apply since queries are arbitrary.

2. Step 2: Recognize the pattern

   Sorting nums and queries allows incremental trie insertion of eligible elements, enabling efficient max XOR queries.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + trie insertion matches known optimal approach [OK]

Hint: Sort queries and nums, then use bit trie [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Using DP for unrelated subproblems
• Greedy max element doesn't guarantee max XOR

2. You are given a list of words and need to find the shortest prefix for each word that uniquely identifies it among all words. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Build a trie where each node tracks how many words pass through it, then find the prefix where frequency is 1.

B. Sort the words and compare only adjacent words to find the shortest unique prefix.

C. Compare each word's prefixes pairwise with all other words to find uniqueness.

D. Use dynamic programming to store prefix uniqueness states for all words.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding shortest unique prefixes efficiently for all words, which suggests a data structure that can share prefixes.

2. Step 2: Evaluate approaches

   Brute force (A) is too slow (O(n^2 * m)). Sorting + adjacent comparison (C) can miss conflicts with non-adjacent words. DP (D) is not a natural fit here. Trie with frequency counts (B) efficiently tracks prefix usage and finds unique prefixes in O(n*m).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie frequency counting matches problem needs [OK]

Hint: Trie frequency counts track prefix uniqueness efficiently [OK]

Common Mistakes:

• Assuming sorting adjacent words is sufficient for uniqueness
• Trying brute force despite inefficiency

3. What is the time complexity of the optimal offline approach that sorts the array and queries, then uses a bit trie to answer maximum XOR queries with constraints?

medium

A. O(n * q)

B. O(n * log M + q * log M)

C. O((n + q) * log M), where M is the max number in nums

D. O(n * log n + q * log q)

Solution

1. Step 1: Identify sorting cost

   Sorting nums and queries costs O(n log n + q log q), but dominated by trie operations.

2. Step 2: Analyze trie insertion and query

   Each insertion and query takes O(log M) where M is max number; total O(n log M + q log M).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting plus trie operations sum to O(n log M + q log M) [OK]

Hint: Trie operations cost O(log M) per element/query [OK]

Common Mistakes:

• Confusing n*q brute force with trie approach
• Ignoring log M factor
• Assuming sorting dominates complexity

4. Suppose you want to extend the Trie to support deletion of words. Which of the following approaches correctly handles deletion without breaking prefix searches for other words?

hard

A. Remove the isEnd flag at the last node of the word and delete nodes bottom-up only if they have no children and isEnd is false

B. Delete all nodes corresponding to the word immediately, regardless of children

C. Set isEnd to false at the last node but never delete any nodes

D. Rebuild the entire trie after each deletion to remove unused nodes

Solution

1. Step 1: Understand deletion impact

   Removing isEnd flag marks word as deleted. Nodes can be deleted only if they are not prefixes of other words.

2. Step 2: Delete nodes bottom-up conditionally

   Delete nodes only if they have no children and isEnd is false to avoid breaking other words.

3. Step 3: Avoid unsafe deletions

   Deleting nodes immediately or rebuilding trie is inefficient or breaks other words.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Conditional bottom-up deletion preserves trie correctness [OK]

Hint: Delete nodes only if no children and isEnd is false [OK]

Common Mistakes:

• Deleting nodes without checking children breaks other words

5. Suppose the Word Break problem is modified so that dictionary words can be reused unlimited times in the segmentation. Which modification to the algorithm is necessary to correctly handle this variant?

hard

A. Modify the inner loop to continue checking all prefixes even after dp[i] is set to True

B. Change dp array to count number of ways instead of boolean flags

C. Remove the dp array and use pure recursion with memoization only

D. No change needed; the original DP with trie approach already supports reuse

Solution

1. Step 1: Understand reuse impact on DP

   When reuse is allowed, multiple segmentations can overlap. The DP must consider all possible prefixes, not stop at first True.

2. Step 2: Modify inner loop behavior

   Breaking early when dp[i] is True prevents exploring all segmentations. Removing the break allows full exploration, correctly handling reuse.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Allowing all prefixes ensures reuse is handled [OK]

Hint: Breaking early blocks multiple reuse paths [OK]

Common Mistakes:

• Assuming original DP supports reuse without change
• Changing dp to count ways unnecessarily
• Removing dp and relying on recursion only