Concatenated Words

📋

Problem

Imagine you have a dictionary of words and want to find which words can be formed by concatenating other words from the same dictionary. This is like checking if a complex password is made by combining simpler known words.

Given an array of strings words (without duplicates), return all the concatenated words in the given list of words. A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

1 ≤ words.length ≤ 10^51 ≤ words[i].length ≤ 30All strings consist of lowercase English letters onlyNo duplicates in words

Edge cases: Empty string in words → should not cause false positivesWords that are prefixes of others but not concatenated → not includedSingle character words repeated → concatenated if combined

</>

IDE

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

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

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

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

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

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

Common Bugs to Avoid

Wrong: catcatsdogcatsdogcatsdogratcatdogcatCounting a single word as concatenated word; missing the requirement that concatenated words must be formed by at least two shorter words.✅ Add a count parameter in recursion and only return true if count >= 2 when the word is fully matched.

Wrong: aTreating single words as concatenated words without verifying multiple components.✅ Ensure that the base case for recursion requires at least two words to form the concatenated word.

Wrong: catsdogGreedy approach picking longest prefix first, missing valid concatenations with shorter prefixes.✅ Try all possible prefixes in recursion instead of only the longest prefix.

Wrong: Restricting word usage to once per concatenation (0/1 knapsack) instead of allowing repeated usage (unbounded).✅ Allow repeated use of words in recursion by not removing words from the set during recursion.

Wrong: Exponential brute force recursion causing TLE on large inputs.✅ Implement memoization or use a trie to prune recursion and reduce complexity to O(n * L^2).

✓

Test Cases

Focus on handling base cases like empty input and single words correctly.

Think about common algorithmic pitfalls like greedy prefix selection and repeated word usage.

Optimize your solution using memoization or trie to handle large inputs efficiently.

t1_01basic

Input{"words":["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]}

Expected["catsdogcats","dogcatsdog","ratcatdogcat"]

⏱ Performance - must finish in 2000ms

"catsdogcats" can be formed by concatenating "cats", "dog", and "cats"; similarly for "dogcatsdog" and "ratcatdogcat".

💡 Think about checking if a word can be split into smaller words from the list.

💡 Use DFS or recursion with memoization to avoid repeated work on the same substrings.

💡 Try building a trie or use a set to quickly check prefixes and memoize results for substrings.

Why it failed: Failed basic test: likely missing the condition that concatenated words must be formed by at least two shorter words. Fix by ensuring count of words used is >= 2 before returning true.

✓ Correctly identifies concatenated words using recursive checks and memoization.

t1_02basic

Input{"words":["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]}

Expected["aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa"]

⏱ Performance - must finish in 2000ms

All words except "a" and "aaaaaaaaaa" can be formed by concatenating smaller "a" words multiple times. "aaaaaaaaaa" cannot be formed by concatenation of at least two shorter words from the list because the only shorter word is "a" and concatenation requires at least two words.

💡 Check if words can be formed by concatenating smaller words multiple times.

💡 Remember that a concatenated word must use at least two shorter words, so single character words alone are not concatenated.

💡 Use memoization to avoid recomputing results for repeated substrings.

Why it failed: Failed to detect repeated concatenations of single character words. Fix by allowing multiple concatenations and ensuring count >= 2.

✓ Correctly handles repeated concatenations of single character words.

t2_01edge

Input{"words":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input list should return empty output.

💡 Consider what happens when the input list is empty.

💡 Your code should handle empty inputs gracefully without errors.

💡 Return an empty list immediately if no words are given.

Why it failed: Code crashes or returns non-empty output on empty input. Fix by adding a check for empty input and returning empty list.

✓ Handles empty input correctly by returning empty list.

t2_02edge

Input{"words":[""]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty string in words should not be considered a concatenated word.

💡 Check how your code treats empty strings in the input.

💡 Empty strings cannot form concatenated words as they have zero length.

💡 Skip or ignore empty strings when checking concatenations.

Why it failed: Empty string treated as concatenated word incorrectly. Fix by ignoring empty strings in the input or ensuring word length > 0 before processing.

✓ Correctly ignores empty strings as concatenated words.

t2_03edge

Input{"words":["cat"]}

Expected[]

⏱ Performance - must finish in 2000ms

Single word cannot be formed by concatenating at least two shorter words.

💡 A single word alone cannot be concatenated from other words.

💡 Ensure your code requires at least two words to form a concatenated word.

💡 Return empty list if no concatenated words found.

Why it failed: Single word incorrectly identified as concatenated. Fix by enforcing count >= 2 in recursion base case.

✓ Correctly returns empty list for single word input.

t3_01corner

Input{"words":["cat","cats","dog","catsdog"]}

Expected["catsdog"]

⏱ Performance - must finish in 2000ms

"catsdog" is concatenated from "cats" and "dog"; greedy approach picking longest prefix first may fail.

💡 Beware of greedy approaches that pick the longest prefix first.

💡 Try all possible splits and use memoization to avoid repeated work.

💡 Backtrack on all prefixes, not just the longest, to find valid concatenations.

Why it failed: Greedy prefix selection fails to find all concatenations. Fix by trying all prefix splits instead of only longest prefix.

✓ Correctly finds concatenated words by exploring all prefix splits.

t3_02corner

Input{"words":["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa","aaaaaaaaaaa"]}

Expected["aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 knapsack and unbounded concatenation: words can be formed by repeated concatenation of smaller words. "aaaaaaaaaaa" cannot be formed by concatenation of at least two shorter words from the list because the only shorter word is "a" and concatenation requires at least two words.

💡 Remember concatenation allows reuse of words multiple times.

💡 Do not limit to using each word only once per concatenation.

💡 Use recursion with memoization to handle repeated use of words.

Why it failed: Incorrectly restricts to 0/1 usage of words, missing repeated concatenations. Fix by allowing multiple uses of words in recursion.

✓ Correctly handles repeated concatenations of words.

t3_03corner

Input{"words":["cat","cats","dog","rat","ratcatdogcat"]}

Expected["ratcatdogcat"]

⏱ Performance - must finish in 2000ms

"ratcatdogcat" is concatenated from multiple words; off-by-one errors in substring indices can cause misses.

💡 Check substring indices carefully when splitting words.

💡 Ensure recursion covers all valid splits without skipping characters.

💡 Use inclusive/exclusive indexing consistently to avoid off-by-one errors.

Why it failed: Off-by-one error in substring splits causes missed concatenations. Fix by verifying substring ranges in recursion.

✓ Correctly handles substring splits without off-by-one errors.

t4_01performance

Input{"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"]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with 100 words of increasing length to test O(n * L^2) complexity; must complete within 2 seconds.

💡 Use memoization or trie to avoid exponential recursion.

💡 Avoid recomputing substring checks by caching results.

💡 Trie traversal combined with DFS reduces complexity to O(n * L^2).

Why it failed: TLE due to exponential brute force recursion without memoization. Fix by implementing memoization or trie-based pruning.

✓ Efficient memoized or trie-based solution passes performance test.

Practice

1. Given the following code snippet for MapSum, after inserting keys "apple" with value 3 and "app" with value 2, what is the value of node.sum at the trie node corresponding to 'p' (the second character) after the second insert?

easy

A. 3

B. 5

C. 2

D. 0

Solution

1. Step 1: Trace insert of "apple" with value 3

   Delta = 3 - 0 = 3. Root.sum += 3 -> 3. For each character 'a','p','p','l','e', node.sum += 3. After first insert, node at second 'p' has sum 3.

2. Step 2: Trace insert of "app" with value 2

   Delta = 2 - 0 = 2. Root.sum += 2 -> 5. For 'a','p','p', node.sum += 2. Node at second 'p' sum was 3, now 3 + 2 = 5.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum at second 'p' after both inserts is 5 [OK]

Hint: Sum accumulates delta on each insert per prefix node [OK]

Common Mistakes:

• Forgetting to add delta on second insert
• Confusing first and second 'p' nodes
• Using old value instead of delta

2. Consider the following Python code snippet implementing the Trie + DFS approach for palindrome pairs. Given the input words = ["bat", "tab", "cat"], what is the final output of palindromePairs(words)?

easy

A. [[0, 1], [1, 0]]

B. [[1, 0], [0, 1]]

C. [[0, 1], [1, 0], [2, 2]]

D. []

Solution

1. Step 1: Trace add_word for "bat" and "tab"

   Words are added reversed: "tab" for "bat", "bat" for "tab". Palindrome suffixes recorded accordingly.

2. Step 2: Trace search for "bat" (index 0)

   Matches "tab" reversed in trie, finds palindrome suffixes leading to pair [0,1]. Similarly for "tab" (index 1) finds [1,0]. "cat" has no pairs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected palindrome pairs [OK]

Hint: Pairs are symmetric for "bat" and "tab" only [OK]

Common Mistakes:

• Confusing order of pairs
• Including self-pairs
• Missing palindrome suffix checks

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. Suppose you want to extend the Trie to support deletion of words. Which of the following approaches correctly handles deletion without breaking prefix searches for other words?

hard

A. Remove the isEnd flag at the last node of the word and delete nodes bottom-up only if they have no children and isEnd is false

B. Delete all nodes corresponding to the word immediately, regardless of children

C. Set isEnd to false at the last node but never delete any nodes

D. Rebuild the entire trie after each deletion to remove unused nodes

Solution

1. Step 1: Understand deletion impact

   Removing isEnd flag marks word as deleted. Nodes can be deleted only if they are not prefixes of other words.

2. Step 2: Delete nodes bottom-up conditionally

   Delete nodes only if they have no children and isEnd is false to avoid breaking other words.

3. Step 3: Avoid unsafe deletions

   Deleting nodes immediately or rebuilding trie is inefficient or breaks other words.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Conditional bottom-up deletion preserves trie correctness [OK]

Hint: Delete nodes only if no children and isEnd is false [OK]

Common Mistakes:

• Deleting nodes without checking children breaks other words

5. Suppose the problem is modified so that words can be reused multiple times in pairs (i.e., pairs like (i, i) are allowed). Which modification to the Trie + DFS approach correctly handles this variant without producing duplicates or missing pairs?

hard

A. Modify add_word to store all occurrences of the same word and allow same index pairs

B. Keep the check that skips pairs with equal indices but add a separate pass to handle reuse pairs

C. Allow same index pairs by removing index checks but filter duplicates after collecting all pairs

D. Remove the check that skips pairs where indices are equal in search and palindrome_suffixes loops

Solution

1. Step 1: Understand reuse allowance

   Allowing pairs (i, i) means removing index inequality checks but risks duplicates.

2. Step 2: Modify search and add_word accordingly

   Removing index checks alone causes duplicates; filtering duplicates after collection ensures correctness.

3. Step 3: Why other options fail

   Removing checks without filtering causes duplicates; separate pass is inefficient; storing all occurrences is unnecessary.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Removing index checks + duplicate filtering handles reuse correctly [OK]

Hint: Allow reuse by removing index checks + filtering duplicates [OK]

Common Mistakes:

• Removing index checks without filtering
• Adding complex separate passes
• Confusing occurrences with indices