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

2. Given the following code snippet implementing the optimal trie-based solution, what is the output of replaceWords(['cat', 'bat', 'rat'], 'the cattle was rattled by the battery')?

easy

A. the cat was rat by the battery

B. the cat was rat by the bat

C. the cattle was rat by the battery

D. the cat was rattled by the battery

Solution

1. Step 1: Trace prefix search for 'cattle'

   Check 'c' -> 'a' -> 't' in trie; 'cat' is a root and shortest prefix, so replace 'cattle' with 'cat'.

2. Step 2: Trace prefix search for 'rattled' and 'battery'

   'rattled' matches 'rat' prefix; 'battery' matches 'bat' prefix. Other words have no prefix match and remain unchanged.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All replaced words correspond to shortest root prefixes [OK]

Hint: Shortest prefix found stops search early [OK]

Common Mistakes:

• Replacing with longer prefix
• Not replacing words without prefix

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. The following code attempts to answer maximum XOR queries with constraints using a bit trie. Which line contains a subtle bug that can cause incorrect results or runtime errors when no nums ≤ m are available?

medium

A. Line: node = node.children[bit]

B. Line: if not node.children[bit]: node.children[bit] = TrieNode()

C. Line: node = self.root

D. Line: if node.children[toggled_bit]:

Solution

1. Step 1: Identify empty trie scenario

   If no nums ≤ m, trie is empty; node.children[bit] can be None.

2. Step 2: Check max_xor traversal

   Line assigning node = node.children[bit] assumes child exists, causing runtime error or wrong result.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Must handle empty child case to avoid errors [OK]

Hint: Check for None before descending trie [OK]

Common Mistakes:

• Ignoring empty trie case
• Assuming children always exist
• Not returning -1 when no valid nums

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