Skip to main content
Talentd

Stream of Characters - Solution & Explanation

HardArrayStringDesignTrie12 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

Design an algorithm that accepts a stream of characters and checks if a suffix of these characters is a string of a given array of strings words.

For example, if words = ["abc", "xyz"] and the stream added the four characters (one by one) 'a', 'x', 'y', and 'z', your algorithm should detect that the suffix "xyz" of the characters "axyz" matches "xyz" from words.

Implement the StreamChecker class:

  • StreamChecker(String[] words) Initializes the object with the strings array words.
  • boolean query(char letter) Accepts a new character from the stream and returns true if any non-empty suffix from the stream forms a word that is in words.

 

Example 1:

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.

Approach Overview

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.

Approach 1: Approach 1: Trie with Reverse Words

This approach utilizes a reversed Trie (prefix tree) to efficiently manage and query suffixes of input characters. By storing the reversed words in a Trie, we can match suffixes of the input stream by querying from the current character backwards. For each character queried, we move through the Trie from those characters up to a certain limit (or until no further match) to see if any of the suffixes match one of the stored words.

The implementation involves creating a Trie that stores each word in reverse. When a query is made, characters are added to a list representing the current stream. We then check from the current end of the stream backwards through the Trie to determine if any suffix matches a word.

Code

PythonJava

Python

Java

Complexity

Time Complexity for insertion: O(N*L), where N is the number of words and L is the maximum length of a word.
Time Complexity for queries: O(Q*L) where Q is the number of queries and L is the maximum length of a word.
Space Complexity: O(N*L) for storing the words in the Trie.

Try this approach in the editor →

Approach 2: Approach 2: Aho-Corasick Automaton

The Aho-Corasick algorithm is useful for searching multiple 'dictionary' words within a text. We build an automaton with all words and query the stream letters. This data structure enables matching of all dictionary words in parallel through a finite state machine that jumps quickly between states even upon mismatches.

This C++ solution implements the Aho-Corasick algorithm:

  • First, insert all reversed words from the list into the automaton.
  • Second, create the 'failure function' links between Trie nodes for efficient backtracking.
  • During each query, the automaton transitions through states, allowing for efficient suffix matching.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity for building: O(N*L), because we insert and construct failure links.
Time Complexity for queries: O(Q*L) leveraging finite state machine transitions.
Space Complexity: O(N*L) due to the state-space storage representing words.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Trie with Reverse Words

Time Complexity for insertion: O(N*L), where N is the number of words and L is the maximum length of a word.
Time Complexity for queries: O(Q*L) where Q is the number of queries and L is the maximum length of a word.
Space Complexity: O(N*L) for storing the words in the Trie.

Approach 2: Aho-Corasick Automaton

Time Complexity for building: O(N*L), because we insert and construct failure links.
Time Complexity for queries: O(Q*L) leveraging finite state machine transitions.
Space Complexity: O(N*L) due to the state-space storage representing words.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Trie with Reverse WordsO(L) per queryO(W * L)Best interview solution when maximum word length is limited
Aho-Corasick AutomatonO(N + matches)O(W * L)Large dictionaries or high-frequency streaming queries

Video Solution

Stream of Characters | LeetCode 1032 | C++, Java, Python • Knowledge Center • 5,179 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Stream of Characters easy or hard?
Stream of Characters is labeled Hard because it combines multiple concepts: trie design, streaming queries, and efficient suffix matching. The reversed-trie insight significantly simplifies the implementation, while the Aho-Corasick automaton represents the fully optimized multi-pattern approach.
Stream of Characters Python/Java solution
The standard Python or Java implementation builds a reversed trie and keeps a buffer of recent characters from the stream. For each query, iterate backward through the buffer while traversing the trie. If a node marked as a word end is reached, return true; otherwise stop when no child exists.
How to solve Stream of Characters in O(n)?
Use the Aho-Corasick automaton for multi-pattern matching. Build a trie of dictionary words and compute failure links so mismatches transition efficiently. Each streamed character advances the automaton in O(1) amortized time, giving total O(N + matches) complexity for N queries.
What is the best approach for Stream of Characters?
The most common solution uses a trie built from reversed dictionary words. Each query checks characters from the stream backward and walks the trie until either a word match is found or traversal fails. This limits work to the maximum word length L, giving O(L) time per query and O(W * L) memory for W words.
Is Stream of Characters asked at Google/Amazon/Meta?
Problems involving trie design and streaming pattern matching appear frequently in interviews at companies like Google, Amazon, and Meta. Stream of Characters specifically tests trie construction, incremental query processing, and efficient suffix matching in a data stream.
What data structure is used in Stream of Characters?
The core data structure is a trie (prefix tree). Words are inserted in reversed order so suffix checks become prefix traversals. Advanced implementations may also use the Aho-Corasick automaton, which extends a trie with failure links for efficient multi-pattern matching.
What is the time complexity of Stream of Characters?
Using the reversed trie approach, each query runs in O(L) time where L is the length of the longest word in the dictionary. Space complexity is O(W * L) to store the trie. With an Aho-Corasick automaton, the entire stream of N queries can be processed in O(N + matches) time.

Ready to solve this problem?

Practice Stream of Characters with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays