Stream of Characters - Solution & Explanation

Problem Overview: You receive a stream of characters one by one. After each query, determine whether the current stream ends with any word from a predefined dictionary. The challenge is supporting fast suffix checks as the stream grows without rechecking the entire history each time.

Approach 1: Trie with Reverse Words (O(L) query time, O(W * L) space)

The key observation is that each query only cares about suffixes of the stream. Instead of storing dictionary words normally, insert their reversed versions into a trie. Maintain a buffer of recently seen characters from the data stream, also processed in reverse order. After each new character arrives, walk the trie starting from the newest character and move backward through the stream. If a node marked as a complete word is reached, the query returns true. Traversal stops early when no matching child exists. If the longest word has length L, each query checks at most L characters, giving O(L) time per query and O(W * L) space for storing W words. This design pattern—reversing inputs to convert suffix matching into prefix matching—is common when combining string processing with trie structures.

Approach 2: Aho-Corasick Automaton (O(N + matches) total query time, O(W * L) space)

When the dictionary is large or queries are extremely frequent, the Aho-Corasick automaton provides a more scalable solution. This algorithm builds a trie of all dictionary words and augments it with failure links that allow the search to transition efficiently when mismatches occur. During preprocessing, construct the trie and compute failure links using BFS. Each incoming character advances the automaton to the next state in O(1) amortized time. If the resulting state corresponds to a terminal node (or reaches one through failure links), a dictionary word ends at the current stream position. Overall processing of N streamed characters takes O(N + total_matches) time with O(W * L) space. This technique is widely used in multi-pattern matching systems such as intrusion detection and text filtering.

Recommended for interviews: The reversed-trie approach is typically expected in interviews because it demonstrates strong understanding of Trie design and efficient suffix matching. It is straightforward to implement and performs well when the maximum word length is small. The Aho-Corasick automaton is more advanced and shows deeper algorithmic knowledge; mentioning it after implementing the trie solution signals strong familiarity with large-scale string matching systems.