Stream of Characters

📋

Stream of Characters

Edge cases:

</>

IDE

def query(self, letter: str) -> bool:public boolean query(char letter)bool query(char letter)function query(letter)

class StreamChecker:
    def __init__(self, words):
        # Write your solution here
        pass
    def query(self, letter: str) -> bool:
        # Write your solution here
        pass

class StreamChecker {
    public StreamChecker(String[] words) {
        // Write your solution here
    }
    public boolean query(char letter) {
        // Write your solution here
        return false;
    }
}

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

class StreamChecker {
public:
    StreamChecker(vector<string>& words) {
        // Write your solution here
    }
    bool query(char letter) {
        // Write your solution here
        return false;
    }
};

class StreamChecker {
    constructor(words) {
        // Write your solution here
    }
    query(letter) {
        // Write your solution here
        return false;
    }
}

Common Bugs to Avoid

Wrong: [true,true,true,true,true,true,true,true,true,true,true,true]Always returning true regardless of suffix matching.✅ Check suffixes properly by traversing the reversed trie and only return true if a word end is reached.

Wrong: [false,false,false,false]Never returning true even when suffix matches exist.✅ Ensure your query method checks all suffixes up to max word length and returns true if any matches.

Wrong: [true]Returning true on empty query stream or no queries.✅ Return empty list or no output if no queries are made; do not assume queries exist.

Wrong: [false,true]Failing to detect single character word matches immediately.✅ Mark trie nodes for single character words and check on each query.

Wrong: [true,true,false]Greedy approach checking only last character, missing overlapping suffixes.✅ Check all suffixes up to max word length by traversing reversed trie from latest query backwards.

✓

Test Cases

Focus on handling boundary inputs like empty queries and single character words.

Think about common algorithmic pitfalls like greedy suffix checks and repeated characters.

Optimize your solution to run in O(Q * L) time using a reversed trie and limited buffer.

t1_01basic

Input{"words":["cd","f","kl"],"queries":["a","b","c","d","e","f","g","h","i","j","k","l"]}

Expected[false,false,false,true,false,true,false,false,false,false,false,true]

⏱ Performance - must finish in 2000ms

After querying 'd', the suffix 'cd' matches a word. After querying 'f', 'f' matches. After querying 'l', 'kl' matches.

💡 Think about checking suffixes of the stream after each query.

💡 Use a trie built from reversed words to efficiently check suffixes.

💡 Maintain a buffer of recent characters up to max word length and traverse the trie backwards.

Why it failed: Incorrect output means suffix matching logic is flawed. Fix by checking suffixes in reverse using a trie of reversed words.

✓ Correctly identifies suffix matches in the query stream.

t1_02basic

Input{"words":["a","ab","abc"],"queries":["a","b","c","d"]}

Expected[true,true,true,false]

⏱ Performance - must finish in 2000ms

Query 'a' matches 'a'; 'ab' matches 'ab'; 'abc' matches 'abc'; 'd' does not match any suffix.

💡 Check if the current stream suffix matches any word exactly.

💡 Remember that shorter words can be suffixes of longer words.

💡 Use a reversed trie and limit buffer length to max word length.

Why it failed: Failing this test means partial suffixes or shorter words are not checked properly. Fix by checking all suffix lengths up to max word length.

✓ Handles nested suffix matches correctly.

t2_01edge

Input{"words":["a","b"],"queries":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty query stream means no queries, so no matches possible.

💡 Consider what happens if no queries are made.

💡 The output should be empty since no query calls occur.

💡 Ensure your code handles empty query arrays gracefully.

Why it failed: Returning non-empty results on empty queries means query handling is incorrect. Fix by returning empty list if no queries.

✓ Correctly handles empty query stream with no output.

t2_02edge

Input{"words":["z"],"queries":["z"]}

Expected[true]

⏱ Performance - must finish in 2000ms

Single character word matches immediately on query 'z'.

💡 Test with single character words for immediate matches.

💡 Check if your trie or lookup supports single letter words.

💡 Ensure query returns true if last character matches a word.

Why it failed: Failing means single character words are not handled. Fix by allowing trie nodes to mark word ends at root children.

✓ Single character word matches correctly.

t2_03edge

Input{"words":["abcde"],"queries":["x","y","z","a","b","c","d","e"]}

Expected[false,false,false,false,false,false,false,true]

⏱ Performance - must finish in 2000ms

Only after full suffix 'abcde' is queried does it match; earlier queries do not match.

💡 Check that partial suffixes do not falsely match.

💡 Confirm that only full words trigger true.

💡 Use max word length to limit buffer and check suffixes.

Why it failed: Returning true before full word matched means partial suffix matching bug. Fix by verifying full suffix length matches word length.

✓ Correctly returns true only after full word suffix matched.

t2_04edge

Input{"words":["a"],"queries":["x","y","z"]}

Expected[false,false,false]

⏱ Performance - must finish in 2000ms

Queries with characters not in any word always return false.

💡 Check that queries with no matching characters return false.

💡 Ensure trie traversal fails gracefully when character not found.

💡 Return false immediately if no suffix matches.

Why it failed: Returning true for queries with no matching characters means traversal logic is incorrect. Fix by returning false if no path in trie.

✓ Correctly returns false for non-matching queries.

t3_01corner

Input{"words":["ab","bc"],"queries":["a","b","c"]}

Expected[false,true,true]

⏱ Performance - must finish in 2000ms

Query 'b' matches suffix 'ab' (last two chars 'ab'), query 'c' matches suffix 'bc'.

💡 Beware of greedy approaches that only check last character.

💡 Check all suffixes up to max word length for matches.

💡 Use reversed trie traversal for each query to find any suffix match.

Why it failed: Greedy approach checking only last character fails here. Fix by checking all suffixes up to max word length.

✓ Correctly identifies multiple overlapping suffix matches.

t3_02corner

Input{"words":["a","aa"],"queries":["a","a"]}

Expected[true,true]

⏱ Performance - must finish in 2000ms

First 'a' matches 'a'; second 'a' matches 'aa' suffix.

💡 Distinguish between 0/1 and unbounded usage of characters.

💡 Ensure buffer accumulates all queries, not just last one.

💡 Traverse trie for all suffix lengths after each query.

Why it failed: Confusing 0/1 with unbounded usage causes missing longer suffix matches. Fix by accumulating full stream buffer and checking all suffixes.

✓ Handles repeated characters and suffixes correctly.

t3_03corner

Input{"words":["xyz"],"queries":["x","y","z","z"]}

Expected[false,false,true,false]

⏱ Performance - must finish in 2000ms

Only after 'z' third query suffix 'xyz' matches; extra 'z' query does not match.

💡 Watch for off-by-one errors in suffix length checks.

💡 Ensure suffix length matches word length exactly.

💡 Check that extra queries do not falsely match previous words.

Why it failed: Off-by-one error causes false positives on extra queries. Fix by verifying suffix length equals word length before returning true.

✓ Correctly handles suffix length boundaries.

t4_01performance

Input{"words":["aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb","cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc","dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd","eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee","ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff","gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg","hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh","iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii","jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj","kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk","llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll","mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm","nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn","oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo","pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp","qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq","rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr","ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss","tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt"],"queries":["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"]}

Expectednull

⏱ Performance - must finish in 2000ms

n=20 words each length 200, Q=40000 queries; O(Q*L) expected to complete within 2s.

💡 Brute force checking all suffixes each query is too slow.

💡 Use a reversed trie and limit buffer to max word length.

💡 Optimize query to O(L) time by traversing trie once per query.

Why it failed: TLE indicates brute force or inefficient suffix checks. Fix by implementing reversed trie with buffer limited to max word length.

✓ Efficient O(Q*L) solution confirmed.

Practice

1. Consider the following Python code implementing the trie + DFS approach to find index pairs of substrings matching words. Given text = "abcab" and words = ["ab", "bc", "ca"], what is the final sorted list res returned by indexPairs(text, words)?

easy

A. [[0,1],[1,2],[3,4]]

B. [[0,1],[1,2],[2,3]]

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

D. [[0,1],[1,2],[2,3],[3,4]]

Solution

1. Step 1: Build the trie from words ["ab", "bc", "ca"]

   The trie has branches for 'a'->'b', 'b'->'c', and 'c'->'a', each marking word_end at the last character.

2. Step 2: DFS from each index in text "abcab"

   From index 0: 'a'->'b' matches "ab" -> [0,1]. From index 1: 'b'->'c' matches "bc" -> [1,2]. From index 2: 'c'->'a' matches "ca" -> [2,3]. From index 3: 'a'->'b' matches "ab" -> [3,4]. From index 4: 'b' no further match.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   All four pairs found and sorted correctly [OK]

Hint: Trace DFS from each index carefully [OK]

Common Mistakes:

• Missing last match at index 3
• Off-by-one in end index

2. What is the time complexity of the optimal Trie + DFS backtracking approach for finding palindrome pairs in a list of n words, each of maximum length k?

medium

A. O(n * k)

B. O(n^2 * k)

C. O(n * k * log n)

D. O(n * k^2)

Solution

1. Step 1: Identify outer and inner loops

   There are n words, each of length k. Trie insertion and search involve iterating over k characters.

2. Step 2: Analyze palindrome checks and DFS

   Palindrome checks on suffixes/prefixes cost O(k) each, done during insertion and search, leading to O(k^2) per word.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Trie + palindrome checks cause quadratic factor in k, linear in n [OK]

Hint: Palindrome checks inside loops cause k^2 factor [OK]

Common Mistakes:

• Assuming brute force O(n^2 * k)
• Ignoring palindrome check cost
• Confusing log n factor

3. If the problem is modified so that words can be concatenated using the same shorter word multiple times (reuse allowed), which change to the Trie + DFS + memoization approach is necessary to correctly find all concatenated words?

hard

A. Keep memoization but ensure that the base case allows concatenations with repeated words

B. Remove memoization to allow repeated exploration of the same indices

C. No change needed; current memoization handles reuse correctly

D. Modify DFS to allow revisiting the same start index multiple times without memoization

Solution

1. Step 1: Understand reuse means words can be concatenated multiple times

   Memoization caches results per start index; reuse is allowed if base case and DFS logic permit repeated words.

2. Step 2: Adjust base case and DFS to allow repeated words but keep memoization for efficiency

   Memoization should remain to avoid exponential calls; base case must allow concatenations with repeated words.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Memoization remains; base case and DFS logic adapt to reuse [OK]

Hint: Memoization is key; only base case and DFS logic need adjustment for reuse [OK]

Common Mistakes:

• Removing memoization causes TLE
• Ignoring base case changes for reuse

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 each letter cell on the board can be reused multiple times within the same word (i.e., no visited marking needed). Which modification to the Trie + DFS algorithm correctly handles this variant without causing infinite loops or incorrect results?

hard

A. Remove visited marking and add a depth limit equal to the maximum word length to prevent infinite recursion.

B. Use BFS instead of DFS to avoid revisiting cells infinitely.

C. Keep visited marking but reset it after each DFS call to allow reuse.

D. Remove visited marking and keep DFS as is; no other changes needed.

Solution

1. Step 1: Understand reuse allows cycles

   Without visited marking, DFS can revisit the same cell infinitely, causing infinite recursion.

2. Step 2: Add depth limit to DFS

   Limiting recursion depth to the maximum word length prevents infinite loops while allowing reuse of cells.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Depth limit bounds recursion, enabling correct search with reuse [OK]

Hint: Depth limit prevents infinite recursion when reuse allowed [OK]

Common Mistakes:

• Removing visited marking without depth limit causes infinite loops
• Keeping visited marking contradicts reuse
• Switching to BFS doesn't solve infinite recursion