How to Solve Stream of Characters

This problem requires designing a data structure that efficiently tracks a stream of characters and checks if the latest suffix matches any word from a given array. Using a trie with reverse word insertion allows O(1) per-character pointer updates, maintaining fast query times even for long streams. The key is handling multiple overlapping suffixes without rescanning the entire stream repeatedly, ensuring both time and space efficiency.

Problem Statement

Design a class StreamChecker that takes an array of strings words during initialization. The class should process a continuous stream of lowercase letters, and for each new character, determine if any suffix of the characters seen so far forms one of the words in words.

For example, given words = ["abc", "xyz"] and a stream that sequentially receives 'a', 'x', 'y', 'z', the StreamChecker should identify that the suffix "xyz" of the stream "axyz" matches the word "xyz". Implement the StreamChecker class with a query method that returns true if the current stream suffix matches any word, false otherwise.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"] [[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]] Output [null, false, false, false, true, false, true, false, false, false, false, false, true]

Explanation StreamChecker streamChecker = new StreamChecker(["cd", "f", "kl"]); streamChecker.query("a"); // return False streamChecker.query("b"); // return False streamChecker.query("c"); // return False streamChecker.query("d"); // return True, because 'cd' is in the wordlist streamChecker.query("e"); // return False streamChecker.query("f"); // return True, because 'f' is in the wordlist streamChecker.query("g"); // return False streamChecker.query("h"); // return False streamChecker.query("i"); // return False streamChecker.query("j"); // return False streamChecker.query("k"); // return False streamChecker.query("l"); // return True, because 'kl' is in the wordlist

Constraints

• 1 <= words.length <= 2000
• 1 <= words[i].length <= 200
• words[i] consists of lowercase English letters.
• letter is a lowercase English letter.
• At most 4 * 104 calls will be made to query.

Solution Approach

Reverse Trie Construction

Insert all words into a trie in reversed order, so that suffix matching becomes prefix traversal in the trie. This transforms the problem into checking prefixes in a reversed stream efficiently.

Stream Pointer Management

Maintain active pointers in the trie for each incoming character. Move existing pointers along trie edges corresponding to the new character and start a new pointer from the root. If any pointer reaches a word end, return true.

Optimized Query Handling

Limit pointer traversal to the maximum word length to prevent unnecessary checks. Store the stream in a fixed-size buffer to efficiently track only recent characters relevant for suffix matching.

Complexity Analysis

Time complexity is O(L) per query where L is the maximum word length, since each query only traverses at most L trie nodes. Space complexity is O(S) for storing the reversed trie and O(L) for the buffer of recent characters, where S is the total number of characters across all words.

What Interviewers Usually Probe

• Pay attention to trie design and reversed insertion for suffix queries.
• Ensure query performance scales with stream length, not total characters seen.
• Be ready to discuss pointer management and memory optimization for active streams.

Common Pitfalls or Variants

Common pitfalls

• Failing to reverse words in the trie, causing inefficient suffix checks.
• Scanning the entire stream each query instead of limiting to maximum word length.
• Not handling overlapping matches, leading to incorrect true/false responses.

Follow-up variants

• Check for multiple streams simultaneously, requiring separate pointer sets per stream.
• Allow wildcard characters in words, introducing more complex trie traversal logic.
• Return all matching words per query instead of just a boolean result.

How GhostInterview Helps

• Provides structured step-by-step guidance to implement reverse trie and active pointers efficiently.
• Highlights exact failure modes, like missing overlapping suffixes or exceeding query time limits.
• Offers pattern-specific debugging tips for array plus string scenarios and buffer management.

Topic Pages

• Array
• String
• Design
• Trie
• Data Stream

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the core idea behind the Stream of Characters problem?

Use a reversed trie to track word suffixes efficiently, converting suffix detection into prefix traversal of incoming characters.

How do I efficiently manage the character stream?

Maintain a fixed-size buffer of recent characters equal to the maximum word length to limit unnecessary checks.

Why reverse the words in the trie?

Reversing allows checking suffixes as prefixes, enabling O(1) traversal per new character with active pointers.

Can overlapping matches affect the results?

Yes, multiple active pointers handle overlapping matches to ensure correct detection of all valid suffixes.

What is the pattern emphasized in this problem?

This problem exemplifies the Array plus String pattern where streams must be matched against a set of predefined words efficiently.