Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 <= 20001 <= words[i].length <= 200words[i] consists of lowercase English letters.letter is a lowercase English letter.4 * 104 calls will be made to query.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Design · Trie
["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"]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1032: Stream of Characters
class Trie {
Trie[] children = new Trie[26];
boolean isEnd = false;
public void insert(String w) {
Trie node = this;
for (int i = w.length() - 1; i >= 0; --i) {
int idx = w.charAt(i) - 'a';
if (node.children[idx] == null) {
node.children[idx] = new Trie();
}
node = node.children[idx];
}
node.isEnd = true;
}
public boolean query(StringBuilder s) {
Trie node = this;
for (int i = s.length() - 1; i >= 0; --i) {
int idx = s.charAt(i) - 'a';
if (node.children[idx] == null) {
return false;
}
node = node.children[idx];
if (node.isEnd) {
return true;
}
}
return false;
}
}
class StreamChecker {
private StringBuilder sb = new StringBuilder();
private Trie trie = new Trie();
public StreamChecker(String[] words) {
for (String w : words) {
trie.insert(w);
}
}
public boolean query(char letter) {
sb.append(letter);
return trie.query(sb);
}
}
/**
* Your StreamChecker object will be instantiated and called as such:
* StreamChecker obj = new StreamChecker(words);
* boolean param_1 = obj.query(letter);
*/
// Accepted solution for LeetCode #1032: Stream of Characters
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);
*/
# Accepted solution for LeetCode #1032: Stream of Characters
class Trie:
def __init__(self):
self.children = [None] * 26
self.is_end = False
def insert(self, w: str):
node = self
for c in w[::-1]:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.is_end = True
def search(self, w: List[str]) -> bool:
node = self
for c in w[::-1]:
idx = ord(c) - ord('a')
if node.children[idx] is None:
return False
node = node.children[idx]
if node.is_end:
return True
return False
class StreamChecker:
def __init__(self, words: List[str]):
self.trie = Trie()
self.cs = []
self.limit = 201
for w in words:
self.trie.insert(w)
def query(self, letter: str) -> bool:
self.cs.append(letter)
return self.trie.search(self.cs[-self.limit :])
# Your StreamChecker object will be instantiated and called as such:
# obj = StreamChecker(words)
# param_1 = obj.query(letter)
// Accepted solution for LeetCode #1032: Stream of Characters
use std::collections::HashMap;
#[derive(PartialEq, Eq, Clone, Debug, Default)]
struct Trie {
children: HashMap<char, Trie>,
end: bool,
}
impl Trie {
fn new() -> Self {
Self::default()
}
fn insert(&mut self, word: String) {
let mut link = self;
for c in word.chars().rev() {
link = link.children.entry(c).or_default();
}
link.end = true;
}
fn search(&self, stream: &[char]) -> bool {
let mut link = self;
for c in stream.iter().rev() {
if let Some(next) = link.children.get(c) {
link = next;
if next.end {
return true;
}
} else {
return false;
}
}
false
}
}
struct StreamChecker {
trie: Trie,
stream: Vec<char>,
}
impl StreamChecker {
fn new(words: Vec<String>) -> Self {
let mut trie = Trie::new();
for s in words {
trie.insert(s);
}
let stream = vec![];
StreamChecker { trie, stream }
}
fn query(&mut self, letter: char) -> bool {
self.stream.push(letter);
self.trie.search(&self.stream)
}
}
#[test]
fn test() {
let words = vec_string!["cd", "f", "kl"];
let mut obj = StreamChecker::new(words);
assert_eq!(obj.query('a'), false);
assert_eq!(obj.query('b'), false);
assert_eq!(obj.query('c'), false);
assert_eq!(obj.query('d'), true);
assert_eq!(obj.query('e'), false);
assert_eq!(obj.query('f'), true);
assert_eq!(obj.query('g'), false);
assert_eq!(obj.query('h'), false);
assert_eq!(obj.query('i'), false);
assert_eq!(obj.query('j'), false);
assert_eq!(obj.query('k'), false);
assert_eq!(obj.query('l'), true);
}
// Accepted solution for LeetCode #1032: Stream of Characters
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #1032: Stream of Characters
// class Trie {
// Trie[] children = new Trie[26];
// boolean isEnd = false;
//
// public void insert(String w) {
// Trie node = this;
// for (int i = w.length() - 1; i >= 0; --i) {
// int idx = w.charAt(i) - 'a';
// if (node.children[idx] == null) {
// node.children[idx] = new Trie();
// }
// node = node.children[idx];
// }
// node.isEnd = true;
// }
//
// public boolean query(StringBuilder s) {
// Trie node = this;
// for (int i = s.length() - 1; i >= 0; --i) {
// int idx = s.charAt(i) - 'a';
// if (node.children[idx] == null) {
// return false;
// }
// node = node.children[idx];
// if (node.isEnd) {
// return true;
// }
// }
// return false;
// }
// }
//
// class StreamChecker {
// private StringBuilder sb = new StringBuilder();
// private Trie trie = new Trie();
//
// public StreamChecker(String[] words) {
// for (String w : words) {
// trie.insert(w);
// }
// }
//
// public boolean query(char letter) {
// sb.append(letter);
// return trie.query(sb);
// }
// }
//
// /**
// * Your StreamChecker object will be instantiated and called as such:
// * StreamChecker obj = new StreamChecker(words);
// * boolean param_1 = obj.query(letter);
// */
Use this to step through a reusable interview workflow for this problem.
Use a simple list or array for storage. Each operation (get, put, remove) requires a linear scan to find the target element — O(n) per operation. Space is O(n) to store the data. The linear search makes this impractical for frequent operations.
Design problems target O(1) amortized per operation by combining data structures (hash map + doubly-linked list for LRU, stack + min-tracking for MinStack). Space is always at least O(n) to store the data. The challenge is achieving constant-time operations through clever structure composition.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.