Stream of Characters solution and explanation
Google
9 more videos on this problem
Stream of Characters | LeetCode 1032 | C++, Java, PythonKnowledge Center · 26:25 · 5K views
Stream Of Characters | Leetcode 1032Pepcoding · 24:48 · 2K views
Stream of Characters | Leetcode 1032 | Leetcode Hard | Live coding session 🔥🔥🔥🔥Coding Decoded · 15:23 · 1K views
stream of characters leetcode | stream of characters leetcode python solutionthecodingworld · 8:02 · 1K views
Stream of Characters🔥 | 3 APPROACHES | Trie | Leetcode 1032Ayushi Sharma · 27:07 · 943 views
LeetCode 1032. Stream of CharactersHappy Coding · 16:06 · 731 views
stream of characters leetcode | leetcode 1032 | brute force | reverse word trieNaresh Gupta · 12:27 · 701 views
Stream of Characters (Leetcode 1032)Coding Interviews · 10:52 · 604 views
Stream of Characters | LeetCode | Trie Solution Explained in DetailTanishq Chaudhary · 15:38 · 584 views
Leetcode - Stream of Characters (Python)Timothy H Chang · 11:20 · 405 views
The problem
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 arraywords.boolean query(char letter)Accepts a new character from the stream and returnstrueif any non-empty suffix from the stream forms a word that is inwords.
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 <= 20001 <= words[i].length <= 200words[i]consists of lowercase English letters.letteris a lowercase English letter.- At most
4 * 104calls 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.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class StreamChecker:
def __init__(self, words):
self.root = TrieNode()
self.stream = []
for word in words:
node = self.root
for char in reversed(word):
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def query(self, letter):
self.stream.append(letter)
node = self.root
for char in reversed(self.stream):
if node.is_end_of_word:
return True
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_wordclass TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEndOfWord = false;
}
class StreamChecker {
TrieNode root = new TrieNode();
StringBuilder stream = new StringBuilder();
public StreamChecker(String[] words) {
for (String word : words) {
TrieNode node = root;
for (int i = word.length() - 1; i >= 0; i--) {
char c = word.charAt(i);
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
node.isEndOfWord = true;
}
}
public boolean query(char letter) {
stream.append(letter);
TrieNode node = root;
for (int i = stream.length() - 1; i >= 0; i--) {
char c = stream.charAt(i);
if (node.children[c - 'a'] == null) {
return false;
}
node = node.children[c - 'a'];
if (node.isEndOfWord) {
return true;
}
}
return false;
}
}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.
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: 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.
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
class AhoCorasick {
public:
struct TrieNode {
unordered_map<char, TrieNode*> children;
TrieNode* fail = nullptr;
bool is_end = false;
};
TrieNode *root = new TrieNode();
void insert(const string &word) {
TrieNode *node = root;
for(char c : word) {
if(!node->children.count(c)) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->is_end = true;
}
void build() {
queue<TrieNode*> q;
root->fail = root;
for(auto &p : root->children) {
p.second->fail = root;
q.push(p.second);
}
while(!q.empty()) {
TrieNode *curr = q.front(); q.pop();
for(auto &p : curr->children) {
char c = p.first;
TrieNode *child = p.second;
TrieNode *fail = curr->fail;
while(fail != root && !fail->children.count(c)) {
fail = fail->fail;
}
if(fail->children.count(c)) {
child->fail = fail->children[c];
} else {
child->fail = root;
}
child->is_end |= child->fail->is_end;
q.push(child);
}
}
}
};
class StreamChecker {
AhoCorasick ac;
AhoCorasick::TrieNode* node;
public:
StreamChecker(vector<string>& words) {
for(const string &word : words) {
ac.insert(word);
}
ac.build();
node = ac.root;
}
bool query(char letter) {
while(node != ac.root && !node->children.count(letter)) {
node = node->fail;
}
if(node->children.count(letter)) {
node = node->children[letter];
}
return node->is_end;
}
};class TrieNode {
constructor() {
this.children = {};
this.isEndOfWord = false;
this.fail = null;
}
}
class StreamChecker {
constructor(words) {
this.root = new TrieNode();
this.node = this.root;
// Insert all words
for (let word of words) {
let node = this.root;
for (let i = word.length - 1; i >= 0; i--) {
const char = word[i];
if (!(char in node.children)) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.isEndOfWord = true;
}
// Build fail links
const q = [this.root];
while (q.length) {
const current = q.shift();
for (let char in current.children) {
let child = current.children[char];
let failNode = current.fail;
while (failNode && !(char in failNode.children)) {
failNode = failNode.fail;
}
if (failNode) {
child.fail = failNode.children[char];
} else {
child.fail = this.root;
}
child.isEndOfWord = child.isEndOfWord || (child.fail && child.fail.isEndOfWord);
q.push(child);
}
}
}
query(letter) {
while (this.node && !(letter in this.node.children)) {
this.node = this.node.fail;
}
if (this.node) {
this.node = this.node.children[letter];
} else {
this.node = this.root;
}
return this.node ? this.node.isEndOfWord : false;
}
}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.
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.
Approach 3: Default Approach
type Trie struct {
children [26]*Trie
isEnd bool
}
func newTrie() Trie {
return Trie{}
}
func (this *Trie) Insert(word string) {
node := this
for i := len(word) - 1; i >= 0; i-- {
idx := word[i] - 'a'
if node.children[idx] == nil {
node.children[idx] = &Trie{}
}
node = node.children[idx]
}
node.isEnd = true
}
func (this *Trie) Search(word []byte) bool {
node := this
for i := len(word) - 1; i >= 0; i-- {
idx := word[i] - 'a'
if node.children[idx] == nil {
return false
}
node = node.children[idx]
if node.isEnd {
return true
}
}
return false
}
type StreamChecker struct {
trie Trie
s []byte
}
func Constructor(words []string) StreamChecker {
trie := newTrie()
for _, w := range words {
trie.Insert(w)
}
return StreamChecker{trie, []byte{}}
}
func (this *StreamChecker) Query(letter byte) bool {
this.s = append(this.s, letter)
return this.trie.Search(this.s)
}
/**
* Your StreamChecker object will be instantiated and called as such:
* obj := Constructor(words);
* param_1 := obj.Query(letter);
*/Complexity comparison
| Approach | Complexity |
|---|---|
| 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. |
| Approach 2: Aho-Corasick Automaton | Time Complexity for building: O(N*L), because we insert and construct failure links. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Trie with Reverse Words | O(L) per query | O(W * L) | Best interview solution when maximum word length is limited |
| Aho-Corasick Automaton | O(N + matches) | O(W * L) | Large dictionaries or high-frequency streaming queries |
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.