Stream of Characters — Reverse Trie for Suffix Matching

Problem Statement#

LeetCode 1032 — Stream of Characters | Difficulty: Hard

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.

Implement the StreamChecker class:

• StreamChecker(words) initialises the data structure with the given words.
• query(letter) returns true if for some k >= 1, the last k characters queried (in order) spell one of the strings in words.

Constraints:

• 1 <= words.length <= 2000
• 1 <= words[i].length <= 200
• words[i] consists of lowercase English letters.
• 1 <= letter <= 4 * 10^4 total queries.
• letter is a lowercase English letter.

Examples:

StreamChecker checker = new StreamChecker(["cd","f","kl"])
checker.query('a')  → false  (a)
checker.query('b')  → false  (ab)
checker.query('c')  → false  (abc)
checker.query('d')  → true   (abcd, "cd" is a suffix)
checker.query('e')  → false
checker.query('f')  → true   ("f" is a suffix)
checker.query('g')  → false
checker.query('h')  → false
checker.query('i')  → false
checker.query('j')  → false
checker.query('k')  → false
checker.query('l')  → true   ("kl" is a suffix)

Why This Problem Matters#

Stream of Characters is the streaming-suffix problem in disguise. It is asked by Amazon, Google, and Bloomberg as a system-design-flavoured question because the structure mirrors profanity filters, real-time intrusion detection, and incremental log scanners.

The key invariant: at any moment we must answer "does the most recent suffix match any pattern?" without rescanning history. A reverse trie plus a bounded sliding buffer gives an elegant O(W) per query, where W is the longest word length. The pattern transfers directly to Aho-Corasick automatons and finite-state pattern matchers.

The Core Insight#

Instead of inserting words forwards, insert each word reversed into a trie. Then for each query character, append it to a buffer (or directly traverse) and walk the trie from the most recent character backwards. The moment we hit an isEnd node, we found a matching suffix.

Why reversal works: a suffix of the stream that equals a word w corresponds, when read right-to-left, to walking from the last character to the first — which is exactly the path of reverse(w) in the reverse trie.

We cap the lookback at the longest word length to keep each query O(W). Beyond that depth, no word can match anyway.

Visual Dry Run#

Words: ["cd", "f", "kl"]. Reverse and insert:

"cd" → "dc": root → d → c (isEnd)
"f"  → "f" : root → f (isEnd)
"kl" → "lk": root → l → k (isEnd)

Stream: a, b, c, d, e, f. Buffer the stream (ring buffer of size = max word length = 2).

query('a'): buffer = [a]
  walk reverse trie from a: root has no 'a' → false
query('b'): buffer = [a,b]
  walk from b: root has no 'b' → false
query('c'): buffer = [a,b,c]
  walk from c: root has no 'c' → false
query('d'): buffer = [b,c,d]   (cap to 2 chars actually [c,d])
  walk from d: root → d, isEnd? no → continue
  next char back is c: d → c, isEnd? YES → return true
query('e'): walk from e: root has no 'e' → false
query('f'): walk from f: root → f, isEnd YES → return true

The match for "cd" is found by walking d (most recent) → c (older). That is exactly why we reversed during insertion.

Solution (Optimal) — Reverse Trie + Bounded Buffer#

Python#

from collections import deque
 
class TrieNode:
    __slots__ = ("children", "is_end")
    def __init__(self):
        self.children = {}
        self.is_end = False
 
class StreamChecker:
    def __init__(self, words: list[str]):
        self.root = TrieNode()
        self.max_len = 0
        for w in words:
            self.max_len = max(self.max_len, len(w))
            node = self.root
            for ch in reversed(w):                  # insert reversed
                node = node.children.setdefault(ch, TrieNode())
            node.is_end = True
        # Bounded buffer of recent characters (most recent at the right)
        self.buffer: deque[str] = deque(maxlen=self.max_len)
 
    def query(self, letter: str) -> bool:
        self.buffer.append(letter)
        node = self.root
        # Walk from most recent (rightmost) to oldest (leftmost)
        for ch in reversed(self.buffer):
            if ch not in node.children:
                return False
            node = node.children[ch]
            if node.is_end:
                return True
        return False

JavaScript#

class StreamChecker {
  constructor(words) {
    this.root = { children: {}, isEnd: false };
    this.maxLen = 0;
    for (const w of words) {
      this.maxLen = Math.max(this.maxLen, w.length);
      let node = this.root;
      for (let i = w.length - 1; i >= 0; i--) {
        const ch = w[i];
        if (!node.children[ch]) node.children[ch] = { children: {}, isEnd: false };
        node = node.children[ch];
      }
      node.isEnd = true;
    }
    this.buffer = [];
  }
 
  query(letter) {
    this.buffer.push(letter);
    if (this.buffer.length > this.maxLen) this.buffer.shift();
    let node = this.root;
    for (let i = this.buffer.length - 1; i >= 0; i--) {
      const ch = this.buffer[i];
      if (!node.children[ch]) return false;
      node = node.children[ch];
      if (node.isEnd) return true;
    }
    return false;
  }
}

Complexity#

• Build: O(sum of word lengths).
• Query: O(W) where W is the longest word length.
• Space: O(sum of word lengths) for the trie + O(W) for the buffer.

Common Mistakes#

1. Inserting words forward — every query would need to scan all suffix start positions, O(W^2) per query.
2. Using a list and shift() — O(N) per shift in JavaScript; use a circular buffer or index pointer.
3. Returning true only at the deepest match — return on the first isEnd reached; that suffix matches.
4. Forgetting to bound the buffer — without bounding, memory grows linearly in stream length.
5. Buffer ordering confusion — the most recent char must be at one end and walked first; mixing this up gives wrong answers.
6. Building a fresh trie inside query — defeats the purpose; trie is built once in the constructor.

Interview Tips#

• Open by stating the streaming nature: "we get one character at a time and must answer immediately."
• Pitch the reverse-trie idea as the geometric dual of forward search — the interviewer will appreciate the symmetry.
• Justify the bounded buffer by the longest word length — beyond that, no match is possible.
• Mention Aho-Corasick as the next-level optimisation if the dictionary is enormous and queries are dense.
• Discuss thread safety: the trie is read-only after construction, so multiple streams can share it. The buffer is per-stream.

Follow-up Questions#

• What if words can be added dynamically? Re-insert into the trie on the fly; bounded buffer size is updated.
• What if you need ALL matches in the suffix, not just one? Continue walking past the first isEnd and collect all isEnd nodes encountered.
• What about case-insensitive matching? Normalise both insertion and query to lowercase.
• Streaming bytes (Unicode)? Use a hash-map trie keyed on code points.
• Can you achieve O(1) amortised per query? Aho-Corasick with failure links does exactly that — at the cost of more setup work.

Key Takeaways#

• Reverse the words at insert time so queries walk newest-to-oldest naturally.
• Bound the buffer at the longest word length — anything older is irrelevant.
• Return true on first isEnd during the walk; do not scan the rest.
• Build the trie once; queries are O(W) regardless of stream length.
• This pattern is the building block for profanity filters and IDS.
• Aho-Corasick is the production upgrade when constant amortised query time is required.