Stream of Characters

Stream of Characters asks you to detect words inside an ever-growing stream of letters. The clever move is to flip your thinking — and the words — around: build a trie of reversed words and walk it backward from each new character.

The slow way first

The naive approach: keep the whole stream as a string, and on every query check whether any word is a suffix of it. If there are W words of total length L, each query costs O(L) — and you do this for every single character forever. On a long stream that is painfully slow, and it re-scans the same tails again and again.

The question to ask: a word ends at the newest letter — so which direction should I read? Backward. The newest letter is the last letter of any candidate word, the one before it is the second-to-last, and so on.

The idea: a trie of reversed words, walked backward

Insert every word into a trie reversed. Now a root-to-node path spells a word from its last letter toward its first. To answer a query, start at the newest streamed char and walk down the trie; for each step move one character earlier in the stream. If you ever land on a word-end marker, a word just finished at the newest letter. If the trie has no matching child, stop early — no word can complete.

The key insight: reversing turns a suffix question into a prefix walk, which a trie does naturally — and the walk dies the instant the trie lacks the next character, so most queries finish in a couple of steps.

Walk through it

Step through the animation. First we build the reversed trie for ["cd", "f", "kl"] → paths dc, f, lk. Then we stream a, b, c, d, e. The early chars find no child at the root and bail. When d arrives we descend to node d, then read the previous char c and descend again — landing on a word-end. That path spells dc, which is cd reversed, so query('d') returns True.

Pseudocode

build phase:
  for each word:
      walk from the root, inserting its letters in REVERSED order
      mark the final node as a word-end
 
query(letter):
  append letter to the stream
  node = root
  for ch in the stream read from newest to oldest:
      if ch is not a child of node:
          return False            # no word can complete
      node = that child
      if node is a word-end:
          return True             # a word just finished
  return False

The Python solution

class StreamChecker:
    def __init__(self, words):
        self.root = {}
        for w in words:
            node = self.root
            for ch in reversed(w):
                node = node.setdefault(ch, {})
            node['$'] = True
        self.stream = []
 
    def query(self, letter):
        self.stream.append(letter)
        node = self.root
        for ch in reversed(self.stream):
            if ch not in node:
                return False
            node = node[ch]
            if '$' in node:
                return True
        return False

• self.root is a nested-dict trie; '$' marks the end of a (reversed) word.
• The build loop inserts each word with reversed(w), so the trie reads last-letter-first.
• query appends the new letter, then reversed(self.stream) walks from the newest char backward.
• if ch not in node: return False is the early exit — the moment the trie has no matching child, no word can complete.
• if '$' in node: return True fires the instant a path matches a whole word; that word ends exactly at the newest letter.

Complexity

Each query costs only O(m), where m is the longest word length, because the backward walk can descend at most that deep before the trie runs out of children. We pay O(L) space for the trie plus O(n) for the stream.

When this pattern shows up

Practice