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. Consider the following Python code snippet implementing the optimal backtracking solution for Expression Add Operators. Given input num = "123" and target = 6, what is the final list of expressions returned by the function?

easy

A. ["1+2+3", "1*2*3"]

B. ["1+2+3", "1*2*3", "12-6"]

C. ["1+2+3", "1*2*3", "1+23"]

D. ["1+2+3", "1*2*3", "1-2+3"]

Solution

1. Step 1: Trace backtrack calls for num="123", target=6

   At index 0, path starts with "1". Then operators +, -, * are tried with "2" and "3". Valid expressions that evaluate to 6 are "1+2+3" and "1*2*3".

2. Step 2: Verify no other expressions equal 6

   Expressions like "12-6" or "1+23" do not evaluate to 6. "1-2+3" equals 2, so not included.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only "1+2+3" and "1*2*3" sum to 6 [OK]

Hint: Trace small input carefully to confirm valid expressions [OK]

Common Mistakes:

• Including invalid expressions with wrong evaluation
• Missing multiplication precedence

2. Consider the following Python code snippet implementing the bitmask backtracking solution for N-Queens. What is the value of col when placing the first queen in row 0 for n=4?

easy

A. 1

B. 3

C. 2

D. 0

Solution

1. Step 1: Calculate initial mask and available_positions

   For n=4, mask = 0b1111. Initially, cols=pos_diags=neg_diags=0, so available_positions = 0b1111.

2. Step 2: Find rightmost 1-bit and compute col

   pos = available_positions & (-available_positions) = 0b0001, so col = bit_length(1) - 1 = 0.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Rightmost bit corresponds to column 0 [OK]

Hint: Rightmost set bit corresponds to lowest column index [OK]

Common Mistakes:

• Off-by-one in bit_length calculation
• Confusing leftmost with rightmost bit
• Misunderstanding bitmask initialization

3. Identify the bug in the following MedianFinder code snippet that causes incorrect median calculation or runtime errors.

medium

A. Line returning median when small_size > large_size

B. Line balancing heaps when small_size > large_size + 1

C. Line with condition: if not self.small or num <= self.small[0]:

D. Line balancing heaps when large_size > small_size

Solution

1. Step 1: Examine heap insertion condition

   small is a max heap simulated by negating values, so top is -small[0]. Comparing num to self.small[0] (positive) is incorrect.

2. Step 2: Correct condition

   Should compare num <= -self.small[0] to correctly decide which heap to push into.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Negation missing in comparison causes wrong heap insertion [OK]

Hint: Remember to negate values when simulating max heap in Python [OK]

Common Mistakes:

• Forgetting to negate values in comparisons
• Not balancing heaps after insertion
• Incorrect median calculation when heaps unbalanced

4. Examine the following buggy code snippet for the bitmask backtracking N-Queens solution. Which line contains the subtle bug that causes incorrect pruning of valid queen placements?

medium

A. Line updating pos_diags and neg_diags with incorrect bit shifts

B. Line extracting rightmost 1-bit from available_positions

C. Line computing available_positions with bitwise negation

D. Line resetting board[row][col] to '.' after recursion

Solution

1. Step 1: Identify diagonal bitmask updates

   pos_diags should be shifted left (<< 1) and neg_diags shifted right (>> 1) after adding pos.

2. Step 2: Spot incorrect shift directions

   The code shifts pos_diags right and neg_diags left, reversing the intended diagonal tracking, causing pruning errors.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Diagonal shifts must match board traversal direction [OK]

Hint: Diagonal bitmask shifts must be << for pos_diags, >> for neg_diags [OK]

Common Mistakes:

• Reversing diagonal bit shifts
• Forgetting to backtrack board state
• Incorrect bitmask negation

5. What is the time complexity of the divide and conquer approach to the Skyline Problem when given n buildings, and why might a common misconception about the complexity be incorrect?

medium

A. O(n log n) because the problem is divided into halves and merged efficiently

B. O(n log n) time but O(n²) space due to storing all intermediate skylines

C. O(n log n) but with additional O(n) space overhead for recursion stack making it O(n log n) space

D. O(n²) because each merge step compares all points in both skylines

Solution

1. Step 1: Identify divide and conquer structure

   The buildings are split into halves recursively, leading to log n levels.

2. Step 2: Analyze merge cost per level

   Each merge step processes all points in the two skylines combined, which sums to O(n) per level.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Divide and conquer with linear merge per level -> O(n log n) time [OK]

Hint: Divide and conquer merges cost O(n) per level over log n levels [OK]

Common Mistakes:

• Assuming merge is O(n²) due to nested loops
• Confusing recursion stack space with time complexity
• Thinking space grows quadratically due to intermediate skylines