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 are given a dictionary of root words and a sentence. For each word in the sentence, you want to replace it with the shortest root word from the dictionary that is a prefix of the word. Which algorithmic approach guarantees the most efficient and correct solution for this problem?

easy

A. Use dynamic programming to find the shortest prefix for each word by building solutions from smaller subproblems.

B. Check each word against all root words in the dictionary by brute force prefix matching.

C. Sort the root words and for each word in the sentence, perform binary search to find the closest prefix root.

D. Build a trie from the root words and for each word in the sentence, search for the shortest prefix in the trie.

Solution

1. Step 1: Understand the problem constraints

   The problem requires replacing words with the shortest root prefix efficiently, which suggests a prefix-based data structure.

2. Step 2: Evaluate approaches

   Brute force and sorting with binary search are less efficient due to repeated prefix checks. Dynamic programming is not suitable as the problem is not about overlapping subproblems but prefix matching. A trie efficiently stores prefixes and allows quick shortest prefix search.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Trie enables O(m*k) prefix search, optimal for this problem [OK]

Hint: Trie is best for prefix-based replacement [OK]

Common Mistakes:

• Thinking DP applies here
• Using brute force without pruning

2. Consider the following code snippet implementing the optimal trie-based solution for shortest unique prefixes. Given the input words = ["dog", "dove", "duck"], what is the output of shortest_unique_prefix(words)?

easy

A. ["do", "dov", "du"]

B. ["d", "dov", "du"]

C. ["dog", "dove", "duck"]

D. ["dog", "dov", "du"]

Solution

1. Step 1: Trace insertion frequencies

   Insert "dog": d(1), o(1), g(1); "dove": d(2), o(2), v(1), e(1); "duck": d(3), u(1), c(1), k(1).

2. Step 2: Find unique prefixes

   For "dog": prefix "dog" (g freq=1) unique; for "dove": prefix "dov" (v freq=1) unique; for "duck": prefix "du" (u freq=1) unique.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefixes match first node with freq=1 [OK]

Hint: Unique prefix ends where node freq equals 1 [OK]

Common Mistakes:

• Stopping prefix too early
• Assuming first letter always unique

3. Consider the following Python code implementing the optimal StreamChecker. Given the words ["cd", "f", "kl"], what is the return value of the query sequence: query('a'), query('b'), query('c'), query('d')? Specifically, what does query('d') return?

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class StreamChecker:
    def __init__(self, words):
        self.root = TrieNode()
        self.max_len = max(len(w) for w in words)
        self.stream = []
        for word in words:
            node = self.root
            for ch in reversed(word):
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.is_word = True

    def query(self, letter):
        self.stream.append(letter)
        if len(self.stream) > self.max_len:
            self.stream.pop(0)
        node = self.root
        for ch in reversed(self.stream):
            if ch not in node.children:
                return False
            node = node.children[ch]
            if node.is_word:
                return True
        return False

sc = StreamChecker(["cd", "f", "kl"])
print(sc.query('a'))
print(sc.query('b'))
print(sc.query('c'))
print(sc.query('d'))

easy

A. False

B. True

C. Raises an exception

D. None

Solution

1. Step 1: Trace the stream buffer after queries

   After queries 'a', 'b', 'c', 'd', the stream buffer contains ['a','b','c','d'], but max_len=2, so oldest letters are popped. After 'c', stream=['b','c'], after 'd', stream=['c','d'].

2. Step 2: Traverse trie with reversed stream

   For query('d'), reversed stream is ['d','c']. Trie has reversed words: 'dc' for 'cd'. Traversing 'd' then 'c' hits is_word=True at 'c' node, so returns True. However, the query sequence is query('a'), query('b'), query('c'), query('d'). The query('c') returns False because 'c' alone is not a word. The query('d') returns True because 'cd' is in the dictionary and the stream buffer contains ['c','d'].

3. Step 3: Check query('d') return value

   Since the query('d') returns True, the correct answer is True.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Stream buffer limited to max word length matches 'cd' suffix [OK]

Hint: Stream buffer limited to max word length [OK]

Common Mistakes:

• Not limiting stream buffer size
• Not reversing words in trie
• Returning false too early

4. Consider the following code snippet implementing the optimal Word Break solution using a reversed trie and iterative DP. Given s = "leetcode" and wordDict = ["leet", "code"], what is the value of dp[8] after the loop completes?

easy

A. False

B. Raises an exception

C. None

D. True

Solution

1. Step 1: Trace dp array updates for s="leetcode"

   dp[0] = True initially. For i=4, substring s[0:4] = "leet" is in dictionary, so dp[4] = True. For i=8, substring s[4:8] = "code" is in dictionary and dp[4] is True, so dp[8] = True.

2. Step 2: Confirm final dp[n] value

   Since the entire string can be segmented, dp[8] = True.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   dp correctly marks segmentable prefixes [OK]

Hint: dp[i] true if prefix s[:i] can be segmented [OK]

Common Mistakes:

• Off-by-one errors in dp indexing
• Not breaking early when dp[i] is true
• Confusing reversed trie traversal

5. Suppose the problem changes: now the stream can contain repeated queries of the same letter, and you want to support queries that allow reusing letters multiple times to form words (e.g., words can be formed by concatenating repeated suffixes). Which modification to the optimal StreamChecker approach correctly supports this reuse without degrading query time significantly?

hard

A. Keep the same reversed trie and stream buffer, but on each query, perform a DFS from the root to find all possible suffix matches allowing repeated traversal of nodes.

B. Modify the trie to store counts of repeated letters and update the stream buffer to track counts, then traverse accordingly.

C. Increase the stream buffer size to the total length of all words to capture all repeated suffixes.

D. Use a suffix automaton or Aho-Corasick automaton instead of a trie to handle repeated patterns efficiently in queries.

Solution

1. Step 1: Understand the reuse requirement

   Allowing repeated letters and concatenations means suffix matching alone is insufficient; need to handle overlapping patterns efficiently.

2. Step 2: Evaluate data structures

   DFS on trie is expensive and can degrade query time. Counting repeated letters is complex and error-prone. Increasing buffer size is inefficient. Suffix automaton or Aho-Corasick automaton efficiently handle repeated patterns and multiple matches.

3. Step 3: Choose optimal solution

   Using suffix or Aho-Corasick automaton supports repeated pattern matching with efficient query time.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Suffix automaton handles repeated substrings efficiently [OK]

Hint: Suffix automaton handles repeated patterns efficiently [OK]

Common Mistakes:

• Trying DFS on trie causing exponential time
• Increasing buffer size unboundedly
• Tracking counts in trie nodes incorrectly