Palindrome Pairs

📋

Problem

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

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

Edge cases: Empty string present → pairs with any palindrome wordSingle character words → always palindrome pairs with themselves reversedWords that are already palindromes → can form pairs with empty string

</>

IDE

def palindromePairs(words: list[str]) -> list[list[int]]:public List<List<Integer>> palindromePairs(List<String> words)vector<vector<int>> palindromePairs(vector<string> &words)function palindromePairs(words)

def palindromePairs(words):
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> palindromePairs(List<String> words) {
        // Write your solution here
        return new ArrayList<>();
    }
}

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

vector<vector<int>> palindromePairs(vector<string> &words) {
    // Write your solution here
    return {};
}

function palindromePairs(words) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Missing pairs involving empty string and palindrome wordsNot handling empty string special case for palindrome pairs✅ Add explicit checks to pair empty string with all palindrome words at different indices

Wrong: Pairs with same index (e.g. [0,0]) includedNot enforcing distinct indices condition✅ Add condition to skip pairs where i == j

Wrong: Only pairs with fully reversed words found, missing partial palindrome pairsGreedy approach checking only full reversed words✅ Check palindrome prefixes and suffixes for partial matches to find all pairs

Wrong: Fails on large input due to timeoutBrute force O(n^2*k) approach used✅ Implement hash map or trie-based approach with O(n*k^2) complexity

Wrong: Misses pairs involving duplicate wordsMapping words to single index instead of all indices✅ Map words to all their indices and check all pairs

✓

Test Cases

Focus on handling empty strings and single word inputs correctly.

Watch out for greedy traps and ensure palindrome prefix/suffix checks.

Optimize your solution to avoid quadratic time complexity.

t1_01basic

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

Expected[[0,1],[1,0],[3,2],[2,4]]

⏱ Performance - must finish in 2000ms

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

💡 Check pairs of words by concatenating and verifying palindrome property.

💡 Use a hash map to find reversed words quickly and check palindrome prefixes/suffixes.

💡 Store indices of words and check for palindrome suffixes/prefixes to form pairs.

Why it failed: Basic case failed - likely missed checking both prefix and suffix palindrome conditions or reversed word lookups. Fix by verifying palindrome on both sides and using a map of reversed words.

✓ Core palindrome pair detection logic is correct.

t1_02basic

Input["bat","tab","cat"]

Expected[[0,1],[1,0]]

⏱ Performance - must finish in 2000ms

'bat' + 'tab' and 'tab' + 'bat' form palindromes; 'cat' forms no palindrome pairs.

💡 Try reversing words and checking if reversed exists in the list.

💡 Check if concatenation of word and reversed word forms palindrome pairs.

💡 Use a dictionary to map reversed words to indices and verify pairs.

Why it failed: Failed to find pairs where reversed words form palindromes. Fix by mapping reversed words and checking pairs correctly.

✓ Correctly identified palindrome pairs from reversed words.

t2_01edge

Input[""]

Expected[]

⏱ Performance - must finish in 2000ms

Single empty string alone cannot form pairs with distinct indices.

💡 Consider how empty strings interact with palindrome pairs.

💡 Empty string pairs with any palindrome word except itself.

💡 Check for empty string presence and pair with palindrome words at different indices.

Why it failed: Missed handling empty string edge case; empty string pairs with palindrome words at different indices. Fix by adding special case for empty string.

✓ Properly handles empty string edge case.

t2_02edge

Input["a"]

Expected[]

⏱ Performance - must finish in 2000ms

Single character word alone cannot form pairs with distinct indices.

💡 Single character words are palindromes themselves.

💡 Pairs require distinct indices; single element means no pairs.

💡 Return empty list when only one word is present.

Why it failed: Incorrectly returned pairs for single element input. Fix by ensuring pairs have distinct indices.

✓ Correctly returns no pairs for single element input.

t2_03edge

Input["a",""]

Expected[[0,1],[1,0]]

⏱ Performance - must finish in 2000ms

Empty string pairs with palindrome 'a' in both orders.

💡 Empty string pairs with any palindrome word.

💡 Check pairs where one word is empty and the other is palindrome.

💡 Add pairs (empty, palindrome) and (palindrome, empty) with distinct indices.

Why it failed: Failed to pair empty string with palindrome words. Fix by adding pairs involving empty string and palindrome words.

✓ Correctly pairs empty string with palindrome words.

t3_01corner

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

Expected[[0,1],[1,0],[3,2],[2,4],[5,4]]

⏱ Performance - must finish in 2000ms

Detects duplicates and pairs correctly; 'lls' repeated at index 5 pairs with 'sssll' at 4.

💡 Check how duplicates affect palindrome pairs.

💡 Ensure indices are distinct and all pairs are found even with duplicates.

💡 Use a map from word to all indices to handle duplicates properly.

Why it failed: Missed pairs involving duplicate words or failed to handle multiple indices. Fix by mapping words to all indices and checking all pairs.

✓ Correctly handles duplicates and finds all palindrome pairs.

t3_02corner

Input["a","abc","cba"]

Expected[[1,2],[2,1]]

⏱ Performance - must finish in 2000ms

'abc' + 'cba' and 'cba' + 'abc' form palindromes; single character 'a' does not form pairs.

💡 Beware of greedy approaches that only check reversed full words.

💡 Check palindrome prefixes and suffixes for partial matches.

💡 Verify all splits of words for palindrome suffix/prefix to find pairs.

Why it failed: Greedy approach failed by only checking full reversed words. Fix by checking palindrome prefixes and suffixes for partial matches.

✓ Correctly finds pairs using palindrome prefix/suffix checks.

t3_03corner

Input["a","aa","aaa"]

Expected[[0,1],[1,0],[0,2],[2,0],[1,2],[2,1]]

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 knapsack style and unbounded; all pairs of palindromic words form pairs.

💡 Check that pairs are distinct indices, no reuse of same index twice.

💡 Avoid counting pairs multiple times or missing pairs due to index reuse.

💡 Ensure pairs (i,j) with i != j are included for all palindrome combinations.

Why it failed: Confused 0/1 constraint by allowing same index pairs or missing pairs. Fix by enforcing i != j and checking all pairs.

✓ Correctly handles all palindrome pairs with distinct indices.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 with max word length 300; brute force O(n^2*k) will TLE; efficient O(n*k^2) or trie-based needed.

💡 Brute force O(n^2*k) is too slow for large n.

💡 Use hash map or trie with palindrome suffix tracking for O(n*k^2).

💡 Optimize palindrome checks and avoid redundant computations.

Why it failed: TLE due to brute force O(n^2*k) complexity. Fix by implementing hash map or trie-based palindrome pair detection.

✓ Efficient O(n*k^2) or better complexity confirmed.

Practice

1. You need to design a data structure that supports adding words and searching for words, where the search query may contain '.' as a wildcard matching any single character. Which algorithmic approach best guarantees efficient search and add operations for this problem?

easy

A. Use a hash set to store all words and perform linear scan with backtracking on search queries containing wildcards.

B. Use a balanced binary search tree to store words and perform prefix-based search with wildcard expansion.

C. Use a trie data structure combined with iterative DFS/backtracking to handle wildcard searches efficiently.

D. Use dynamic programming to precompute all possible wildcard matches for each word and store results for quick lookup.

Solution

1. Step 1: Understand the problem requirements

   The data structure must support adding words and searching with '.' wildcards that match any character.

2. Step 2: Evaluate algorithmic approaches

   A trie with iterative DFS/backtracking efficiently supports prefix and wildcard searches by exploring only relevant branches, unlike brute force or DP which are inefficient or infeasible.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Trie with backtracking handles '.' wildcard efficiently [OK]

Hint: Trie + backtracking handles wildcards efficiently [OK]

Common Mistakes:

• Thinking brute force with backtracking is efficient enough
• Confusing DP with trie for wildcard search
• Assuming BST supports wildcard search efficiently

2. You need to design a data structure that efficiently supports insertion of strings, exact search for strings, and prefix-based search queries. Which of the following data structures guarantees optimal time complexity for these operations regardless of the number of stored strings?

easy

A. Hash Set storing all strings for O(1) average search but no efficient prefix search

B. Trie (Prefix Tree) that stores characters in nodes with links to children nodes

C. Sorting all strings and using binary search for prefix queries

D. Using a balanced binary search tree keyed by entire strings

Solution

1. Step 1: Understand operation requirements

   Insertion, exact search, and prefix search must be efficient. Hash sets provide O(1) average search but cannot efficiently support prefix queries.

2. Step 2: Compare data structures

   Tries store characters in nodes allowing O(m) time for insert/search/startsWith, where m is length of word or prefix. Binary search on sorted strings is O(m log n) and BSTs do not support prefix queries efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Trie supports prefix queries in O(m) time [OK]

Hint: Tries enable prefix queries in O(m) time [OK]

Common Mistakes:

• Confusing hash sets as supporting prefix queries efficiently

3. You are building a feature that, given a list of product names and a search query typed character-by-character, returns up to three lexicographically smallest products starting with the current prefix after each character is typed. Which algorithmic approach best guarantees efficient retrieval of these suggestions for every prefix?

easy

A. Build a trie from the sorted product list and store up to three suggestions at each node to retrieve suggestions efficiently.

B. Use a brute force approach that filters and sorts the entire product list for each prefix typed.

C. Apply dynamic programming to precompute all possible prefix matches and their top suggestions.

D. Use a greedy algorithm that picks the first three products starting with the prefix without sorting.

Solution

1. Step 1: Understand the problem requirements

   The problem requires returning up to three lexicographically smallest products for every prefix of the search word efficiently.

2. Step 2: Evaluate algorithmic approaches

   Brute force filtering and sorting for each prefix is inefficient. Dynamic programming is not suitable for prefix-based retrieval. A greedy approach without sorting fails lex order requirements. Building a trie with stored top 3 suggestions at each node allows O(m) retrieval where m is prefix length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie with stored suggestions matches problem constraints and efficiency [OK]

Hint: Trie with stored suggestions enables fast prefix queries [OK]

Common Mistakes:

• Assuming brute force is efficient enough
• Confusing DP with prefix search
• Ignoring lexicographic order in greedy approach

4. What is the time complexity of the optimal bitwise trie approach to count pairs with XOR in a range for an input array of size n and maximum number M (max element)?

medium

A. O(n * log M)

B. O(n^2)

C. O(n * M)

D. O(n * log n)

Solution

1. Step 1: Identify operations per element

   Each number is inserted into the trie in O(log M) time, where M is the max number (bit length).

2. Step 2: Query per element also takes O(log M)

   For each number, querying the trie for counts less than a limit also takes O(log M).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall complexity is O(n * log M) due to insert and query per element [OK]

Hint: Trie operations scale with bit length, not array size squared [OK]

Common Mistakes:

• Assuming O(n^2) due to pairs
• Confusing M with n in complexity
• Ignoring log factor from bit length

5. What is the time complexity of processing Q queries using the optimal StreamChecker approach that builds a trie of reversed words and maintains a stream buffer limited to the maximum word length L? Assume W words with maximum length L. Choose the most accurate complexity.

medium

A. O(Q * W * L)

B. O(Q * L^2)

C. O(Q * L)

D. O(Q + W * L)

Solution

1. Step 1: Identify operations per query

   Each query appends a letter and traverses at most L nodes in the trie (limited by max word length).

2. Step 2: Calculate total complexity

   Building the trie takes O(W * L) once. Each query takes O(L) time. Total is O(Q * L) for queries plus O(W * L) for setup, dominated by O(Q * L) for large Q.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Traversal limited to max word length L per query [OK]

Hint: Traversal limited to max word length L per query [OK]

Common Mistakes:

• Confusing brute force O(Q*W*L) with trie approach
• Assuming quadratic in L
• Ignoring trie build cost