Stream of Characters

▶

Steps

setup

Initialize Trie Root and Determine Max Word Length

Create the root node of the trie and compute the maximum length among the input words to limit the stream buffer size.

💡 Knowing the max word length allows efficient buffer management, avoiding unnecessary memory growth.

Line:

self.root = TrieNode()
self.max_len = max(len(w) for w in words)

💡 The max word length sets the buffer size limit for suffix checking.

insert

Insert Word 'cd' Reversed into Trie

Insert the reversed word 'dc' into the trie by creating nodes for 'd' and 'c' and marking the last node as end of word.

💡 Inserting reversed words allows suffix queries to be checked by traversing from the stream's end backwards.

Line:

for ch in reversed(word):
  if ch not in node.children:
    node.children[ch] = TrieNode()
  node = node.children[ch]
node.is_word = True

💡 Each character is inserted as a child node, building the reversed path for 'cd'.

insert

Insert Word 'f' Reversed into Trie

Insert the reversed word 'f' by adding a child node 'f' to the root and marking it as end of word.

💡 Single character words are inserted similarly, enabling quick suffix matches for single letters.

Line:

for ch in reversed(word):
  if ch not in node.children:
    node.children[ch] = TrieNode()
  node = node.children[ch]
node.is_word = True

💡 The trie now contains a branch for 'f' as a complete word.

insert

Insert Word 'kl' Reversed into Trie

Insert the reversed word 'lk' by adding nodes for 'l' and 'k' and marking 'k' as end of word.

💡 Longer words are inserted character by character, building deeper branches in the trie.

Line:

for ch in reversed(word):
  if ch not in node.children:
    node.children[ch] = TrieNode()
  node = node.children[ch]
node.is_word = True

💡 The trie now has three branches for the reversed words 'dc', 'f', and 'lk'.

traverse

Query 'a': Append to Stream Buffer

Append letter 'a' to the stream buffer. Buffer now contains ['a'].

💡 The stream buffer stores recent letters up to max word length for suffix checking.

Line:

self.stream.append(letter)
if len(self.stream) > self.max_len:
  self.stream.pop(0)

💡 Buffer management ensures only relevant recent letters are kept.

traverse

Query 'a': Traverse Trie for 'a'

Check if 'a' exists as a child of root. It does not, so return false.

💡 If the first character in reversed buffer is not in trie children, no suffix matches.

Line:

for ch in reversed(self.stream):
  if ch not in node.children:
    return False

💡 Early termination avoids unnecessary traversal when no match is possible.

traverse

Query 'c': Append and Traverse

Append 'c' to buffer ['a','b','c']. Traverse trie starting from root checking 'c'.

💡 Traversal tries to match suffixes starting from the newest letter backwards.

Line:

self.stream.append(letter)
if len(self.stream) > self.max_len:
  self.stream.pop(0)
node = self.root
for ch in reversed(self.stream):

💡 Traversal continues if character found in children.

traverse

Query 'd': Append and Traverse to Match 'cd'

Append 'd' to buffer ['a','b','c','d']. Traverse trie checking 'd' then 'c' backwards, finding a word match.

💡 Matching reversed suffix 'dc' corresponds to word 'cd' in original order.

Line:

for ch in reversed(self.stream):
  if ch not in node.children:
    return False
  node = node.children[ch]
  if node.is_word:
    return True

💡 Suffix match found by traversing reversed buffer in trie.

traverse

Query 'f': Append and Traverse to Match 'f'

Append 'f' to buffer and traverse trie checking 'f' at root children, finding a word match immediately.

💡 Single letter words match quickly if the letter is a direct child of root with is_word true.

Line:

for ch in reversed(self.stream):
  if ch not in node.children:
    return False
  node = node.children[ch]
  if node.is_word:
    return True

💡 Single letter suffix matches are detected immediately.

traverse

Query 'k': Append and Traverse

Append 'k' to buffer and traverse trie checking 'k' at root children. 'k' not found, traversal stops with false.

💡 If the newest letter is not a child of root, no suffix matches start with it.

Line:

for ch in reversed(self.stream):
  if ch not in node.children:
    return False

💡 Traversal quickly rejects non-matching suffixes.

traverse

Query 'l': Append and Traverse to Match 'kl'

Append 'l' to buffer and traverse trie checking 'l' then 'k' backwards, finding a word match.

💡 Traversal follows reversed suffix 'lk' to find the word 'kl'.

Line:

for ch in reversed(self.stream):
  if ch not in node.children:
    return False
  node = node.children[ch]
  if node.is_word:
    return True

💡 Suffix match found by traversing reversed buffer in trie.

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

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

    def query(self, letter):
        self.stream.append(letter)  # STEP 5,7,8,9,10,11
        if len(self.stream) > self.max_len:  # STEP 5,7,8,9,10,11
            self.stream.pop(0)  # STEP 5,7,8,9,10,11
        node = self.root  # STEP 6,8,9,10,11
        for ch in reversed(self.stream):  # STEP 6,8,9,10,11
            if ch not in node.children:  # STEP 6,10
                return False  # STEP 6,10
            node = node.children[ch]  # STEP 8,9,11
            if node.is_word:  # STEP 8,9,11
                return True  # STEP 8,9,11
        return False  # STEP 6,10

if __name__ == "__main__":
    sc = StreamChecker(["cd", "f", "kl"])  # STEP 1-4
    queries = ['a','b','c','d','e','f','g','h','i','j','k','l']  # STEP 5-11
    results = [sc.query(ch) for ch in queries]  # STEP 5-11
    print(results)  # STEP 11

📊

Stream of Characters - Watch the Algorithm Execute, Step by Step

Watching each query and trie traversal visually reveals how suffix matching works efficiently with a reversed trie and limited buffer.

insert

insert

cd

dc*

insert

f

dc*f*

insert

kl

dc*f*lk*

search

a

dc*f*lk*

Search: false

search

a

dc*f*lk*

Search: false

search

c

dc*f*lk*

Search: false

search

cd

dc*f*lk*

Search: true

search

f

dc*f*lk*

Search: true

search

k

dc*f*lk*

Search: false

search

kl

dc*f*lk*

Search: true

Key Takeaways

✓ Reversing words in the trie allows efficient suffix matching by traversing the stream buffer backwards.

This insight is hard to see from code alone because the reversal logic is implicit and the traversal direction is opposite to normal prefix tries.

✓ Limiting the stream buffer to the maximum word length keeps the algorithm efficient and memory usage bounded.

Without this, the buffer could grow indefinitely, making suffix checks slower and more memory intensive.

✓ Traversal stops early when a character is not found in the trie children, avoiding unnecessary checks.

This early pruning is a key optimization that speeds up queries, but is subtle in code and clearer when visualized.

Practice

1. You are given a list of words and need to find the longest word such that every prefix of the word is also in the list. Which approach guarantees an optimal solution for this problem?

easy

A. Sort the words by length and lex order, then check prefixes using a hash set.

B. Apply a greedy approach by always choosing the lexicographically smallest prefix at each step.

C. Use dynamic programming to build the longest word by extending smaller valid words.

D. Build a trie from the words and perform a BFS traversal to find the longest valid word.

Solution

1. Step 1: Understand the prefix condition

   The problem requires that every prefix of the candidate word must be present in the list, which naturally fits a trie structure where each node represents a prefix.

2. Step 2: Why BFS on trie works best

   BFS traversal on the trie allows level-by-level exploration, ensuring that only nodes representing complete words are considered, thus guaranteeing the longest word with all prefixes present is found efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Trie + BFS directly encodes prefix checks and finds longest word [OK]

Hint: Trie BFS ensures prefix validity and longest word [OK]

Common Mistakes:

• Assuming greedy lex order always works
• Using DP without prefix structure
• Checking prefixes inefficiently without trie

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. What is the worst-case time complexity of searching for a word of length m in a trie implemented with a hash map for children, assuming the alphabet size is large and the trie contains n words?

medium

A. O(m) because each character leads to a hash map lookup

B. O(m * log n) due to hash map lookup cost increasing with n

C. O(n * m) because each search may scan all words

D. O(m * |alphabet|) because each character requires scanning all children

Solution

1. Step 1: Identify search steps in trie

   Search traverses nodes for each character in the word, performing a hash map lookup per character.

2. Step 2: Analyze hash map lookup cost

   Hash map lookup is O(1) average, so total time is O(m) where m is word length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Search time depends on word length, not number of stored words [OK]

Hint: Trie search time depends on word length, not number of words [OK]

Common Mistakes:

• Confusing trie search with scanning all words (O(n*m))

4. Consider the following buggy code snippet for the longest word in dictionary problem. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line: queue.append(child) without checking if child.word is not None

B. Line: for ch in sorted(node.children.keys())

C. Line: node.word = word in insert method

D. Line: trie.insert(word) in the for loop

Solution

1. Step 1: Identify enqueue condition

   The BFS queue should only include nodes representing complete words (child.word != None) to ensure all prefixes are valid.

2. Step 2: Locate the bug

   The code enqueues all children regardless of whether they represent complete words, allowing invalid prefixes to be considered, breaking the prefix condition.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Enqueueing invalid prefix nodes causes incorrect longest word [OK]

Hint: Only enqueue nodes with complete words in BFS [OK]

Common Mistakes:

• Enqueueing all children regardless of word completion
• Misplacing word assignment in insert
• Sorting children incorrectly

5. What is the time complexity of the sum(prefix) operation in the optimal MapSum implementation using a trie with array children, assuming average key length is k and n keys inserted?

medium

A. O(n * k) because we must scan all keys to sum prefix matches.

B. O(k) because we traverse the trie nodes corresponding to the prefix length.

C. O(k * 26) because we check all children at each prefix node.

D. O(log n) because trie nodes are balanced like a BST.

Solution

1. Step 1: Identify sum operation steps

   Sum traverses trie nodes along prefix characters only, no scanning of all keys.

2. Step 2: Analyze traversal cost

   Each character leads to one child node via array index, so traversal is O(k) where k is prefix length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum is O(k) due to direct trie traversal [INCORRECT]

Hint: Sum only traverses prefix length nodes, not all keys [INCORRECT]

Common Mistakes:

• Confusing sum with brute force scanning
• Thinking all children checked at each node
• Assuming trie is balanced BST