Index Pairs of a String

📋

Index Pairs of a String

Edge cases:

</>

IDE

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

def indexPairs(text, words):
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> indexPairs(String text, String[] words) {
        // Write your solution here
        return new ArrayList<>();
    }
}

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

vector<vector<int>> indexPairs(string text, vector<string> words) {
    // Write your solution here
    return {};
}

function indexPairs(text, words) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[0,2]]Only returning longest match per start index, missing shorter matches.✅ Collect all matches found during trie traversal at each start index, not just the longest.

Wrong: [[0,1],[2,3]]Stopping traversal after first match per start index, missing overlapping matches.✅ Continue trie traversal after each match to find all possible matches starting at that index.

Wrong: [[0,0],[1,1]]Ignoring longer matches and only matching single characters.✅ Traverse trie fully to find all matches of varying lengths starting at each index.

Wrong: Non-empty output when words list is emptyNot handling empty words list input properly.✅ Add check to return empty list immediately if words is empty.

Wrong: Timeout or crash on large inputUsing brute force substring checking instead of trie-based search.✅ Implement trie construction and search from each index with pruning to achieve O(n*m) complexity.

✓

Test Cases

Focus on handling empty and minimal inputs correctly.

Think about overlapping matches and multiple matches per start index.

Optimize your approach to avoid brute force substring checks.

t1_01basic

Input{"text":"thestoryofleetcodeandme","words":["story","fleet","leetcode"]}

Expected[[3,7],[9,13],[10,17]]

⏱ Performance - must finish in 2000ms

The substrings "story" (indices 3-7), "fleet" (9-13), and "leetcode" (10-17) appear in text.

💡 Try checking each substring of text against the words list.

💡 Use a trie to efficiently find all words starting at each index.

💡 Build a trie from words, then for each index in text, traverse trie to find matches.

Why it failed: Output missing or incorrect pairs; likely not checking all substrings or not sorting results. Fix by building a trie and searching from each index, then sort pairs by start and end indices.

✓ Correctly finds all matching substrings and returns sorted pairs.

t1_02basic

Input{"text":"ababa","words":["aba","ab"]}

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

⏱ Performance - must finish in 2000ms

Matches "ab" at [0,1] and [2,3], and "aba" at [0,2] and [2,4].

💡 Check for overlapping matches starting at each index.

💡 Trie traversal from each position can find multiple matches of different lengths.

💡 Ensure to collect all matches, not just the longest or first found.

Why it failed: Missing overlapping matches or only returning longest match per start index. Fix by collecting all matches found during trie traversal from each start index.

✓ All overlapping matches correctly found and returned sorted.

t2_01edge

Input{"text":"abc","words":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty words list means no matches possible, so output is empty list.

💡 What if words list is empty? No matches can be found.

💡 Check if your code handles empty words input gracefully.

💡 Return empty list immediately if words is empty.

Why it failed: Code crashes or returns non-empty output when words list is empty. Fix by adding a check to return empty list if words is empty.

✓ Correctly returns empty list when words list is empty.

t2_02edge

Input{"text":"a","words":["a"]}

Expected[[0,0]]

⏱ Performance - must finish in 2000ms

Single character text and word match at index 0.

💡 Test with minimal input size: single character text and word.

💡 Ensure your code handles single character matches correctly.

💡 Trie should handle single node and match at position 0.

Why it failed: Fails to find matches when text or words have length 1. Fix by handling single character words and text correctly in trie traversal.

✓ Correctly finds single character matches.

t2_03edge

Input{"text":"aaaaa","words":["a","aa","aaa"]}

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

⏱ Performance - must finish in 2000ms

All occurrences of 'a', 'aa', and 'aaa' substrings found at all valid positions.

💡 Check if your code finds all overlapping matches in repeated character text.

💡 Trie traversal should continue after each match to find longer matches.

💡 Collect all matches at each start index, not just first or longest.

Why it failed: Misses overlapping matches or stops traversal too early. Fix by continuing trie traversal after each match to find all possible matches.

✓ All overlapping matches in repeated characters found correctly.

t2_04edge

Input{"text":"","words":["a"]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty text means no substrings to match, so output is empty list.

💡 Check how your code handles empty text input.

💡 No substrings exist in empty text, so no matches possible.

💡 Return empty list immediately if text is empty.

Why it failed: Code crashes or returns non-empty output when text is empty. Fix by adding a check to return empty list if text is empty.

✓ Correctly returns empty list when text is empty.

t3_01corner

Input{"text":"abcde","words":["ab","bc","cd","de"]}

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

⏱ Performance - must finish in 2000ms

Matches are adjacent pairs overlapping by one character each.

💡 Check if your code handles overlapping matches correctly.

💡 Trie traversal must restart at each index and find all matches starting there.

💡 Do not skip indices after finding a match; continue scanning all positions.

Why it failed: Greedy approach that stops after first match per start index misses others. Fix by continuing trie traversal fully at each start index.

✓ All overlapping adjacent matches found correctly.

t3_02corner

Input{"text":"aaaaa","words":["a","aa"]}

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

⏱ Performance - must finish in 2000ms

Multiple matches of different lengths starting at same indices, testing unbounded vs 0/1 confusion.

💡 Check if your code mistakenly treats matches as 0/1 occurrences instead of all occurrences.

💡 Trie traversal should find all matches starting at each index, not just one.

💡 Collect all matches found during traversal, not just first or longest.

Why it failed: Confusing 0/1 vs unbounded matching causes missing matches. Fix by collecting all matches found during trie traversal at each start index.

✓ All matches including overlapping and multiple lengths found correctly.

t3_03corner

Input{"text":"abc","words":["abcd"]}

Expected[]

⏱ Performance - must finish in 2000ms

Word longer than any substring in text; no matches possible.

💡 Check if your code handles words longer than text substrings gracefully.

💡 Trie traversal should stop when text substring ends before word ends.

💡 Return empty list if no matches found.

Why it failed: Code crashes or returns invalid matches when word length exceeds text substring length. Fix by stopping traversal when text ends.

✓ Correctly returns empty list when no matches possible.

t4_01performance

Input{"text":"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","words":["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa","aaaaaaaaaaa","aaaaaaaaaaaa","aaaaaaaaaaaaa","aaaaaaaaaaaaaa","aaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, words up to length 100; O(n*m) trie approach must complete within 2s.

💡 Brute force O(n^2*m) will time out on large input.

💡 Use trie to reduce search complexity to O(n*m).

💡 Implement early pruning in trie traversal to improve performance.

Why it failed: Brute force or naive substring checking causes TLE. Fix by building a trie and searching from each index with pruning.

✓ Efficient trie-based solution runs within time limit.

Practice

1. You are given an array of integers and a range [low, high]. You need to count the number of pairs (i, j) with i < j such that the XOR of nums[i] and nums[j] lies within the given range. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Use a brute force nested loop to check all pairs and count those with XOR in the range.

B. Use dynamic programming to store counts of XOR values for prefixes and combine them.

C. Sort the array and use two pointers to find pairs with XOR in the range.

D. Build a bitwise trie of the numbers and for each number, query how many previously inserted numbers produce XOR less than or equal to a limit, then combine results for the range.

Solution

1. Step 1: Understand the problem constraints

   The problem requires counting pairs with XOR in a range efficiently, which brute force (nested loops) is too slow for large inputs.

2. Step 2: Identify the suitable data structure

   A bitwise trie allows efficient counting of numbers with XOR less than a limit by traversing bits from most significant to least significant.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitwise trie approach is known to solve XOR range queries optimally [OK]

Hint: Bitwise trie enables efficient XOR range counting [OK]

Common Mistakes:

• Thinking sorting + two pointers works for XOR ranges
• Assuming DP can handle XOR pairs directly
• Believing brute force is optimal

2. You are given a list of unique words and need to find all pairs of distinct indices (i, j) such that concatenating words[i] + words[j] forms a palindrome. Which algorithmic approach guarantees an optimal solution in terms of time complexity for this problem?

easy

A. Brute force checking all pairs and verifying palindrome by concatenation

B. Building a Trie of reversed words and using DFS/backtracking to find palindrome pairs

C. Dynamic programming to find longest palindromic subsequences in concatenated strings

D. Greedy approach by sorting words and matching prefixes and suffixes

Solution

1. Step 1: Understand problem constraints

   The problem requires checking pairs of words to find palindrome concatenations efficiently.

2. Step 2: Evaluate approaches

   Brute force is O(n^2 * k), DP for subsequences doesn't directly solve pairs, greedy fails on complex cases. Trie + DFS exploits reversed words and palindrome suffixes for O(n * k^2) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Trie + DFS is known optimal for palindrome pairs [OK]

Hint: Trie + DFS exploits reversed words efficiently [OK]

Common Mistakes:

• Assuming brute force is optimal
• Confusing palindrome subsequence DP with pairs
• Thinking greedy prefix matching suffices

3. 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

4. Examine the following buggy code snippet for building the trie and collecting suggestions. Which line contains the subtle bug that can cause incorrect suggestion ordering or runtime errors?

medium

A. Line with 'products.sort()' missing before building trie

B. Line with 'for product in products:' loop

C. Line with 'if len(node.suggestions) < 3:' condition

D. Line with 'if node and ch in node.children:' during search

Solution

1. Step 1: Identify missing sorting

   The code does not sort products before building the trie, so suggestions are appended in input order, not lex order.

2. Step 2: Consequences of missing sort

   Without sorting, the suggestions list at each node is not guaranteed to be lexicographically smallest three, violating problem requirements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting before trie build is essential for correct lex order [OK]

Hint: Always sort products before building trie for lex order [OK]

Common Mistakes:

• Forgetting to sort products
• Appending suggestions without limit
• Not handling missing prefix nodes

5. Suppose the problem is modified so that pairs can be counted multiple times if elements are reused (i.e., pairs (i, j) with i and j possibly equal). Which modification to the bitwise trie approach correctly handles this scenario?

hard

A. Modify the query function to include the current number in the trie before querying to count pairs with itself.

B. No change needed; the existing approach already counts pairs with reuse.

C. Insert all numbers into the trie first, then for each number query the trie for counts less than limit, allowing reuse.

D. Use a frequency map instead of a trie since reuse breaks trie assumptions.

Solution

1. Step 1: Understand reuse means pairs can include the same element twice

   Counting pairs with i == j means the current number must be considered in queries.

2. Step 2: Modify insertion and query order

   Insert the current number into the trie before querying so it can pair with itself and others, enabling reuse counting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inserting before querying allows counting pairs including the current element [OK]

Hint: Insert before query to count pairs with reuse [OK]

Common Mistakes:

• Assuming no change needed
• Inserting after query (misses self pairs)
• Switching to frequency map unnecessarily