AlgoMaster Logo

Stream of Characters

hardFrequencyUpdated September 21, 2026

Understanding the Problem

This is a string matching task with one complication: we are not given the full string upfront. Characters arrive one at a time through the query method, and after each character, we need to check whether any word from our dictionary appears as a suffix of everything we have seen so far.

A suffix of the stream is any substring that ends at the current position. If we have queried 'a', 'b', 'c', 'd' in sequence, the stream is "abcd" and its suffixes are "d", "cd", "bcd", and "abcd". We need to check whether any of these matches a word in our dictionary.

The naive approach stores the entire stream and checks every possible suffix against the word list after each query. With up to 40,000 queries and words up to 200 characters long, that repeated substring work is the bottleneck. A Trie built from the reversed words removes it: we search backward through the stream once, checking every possible suffix match in a single traversal.

Key Constraints:

  • words.length <= 2000 and words[i].length <= 200 → The total number of characters across all words is at most 400,000, which bounds the size of a Trie built from them.
  • At most 4 * 10^4 calls to query → Each query must be efficient. We cannot rescan all words from scratch on every call.
  • words[i].length <= 200 → This caps the depth of the Trie and the number of characters we look back in the stream per query at 200.

Approach 1: Brute Force (HashSet + Suffix Checking)

Intuition

Store all the words in a HashSet for O(1) lookup, keep a running buffer of every queried character, and after each new character check every possible suffix of the buffer against the set.

Since words are at most 200 characters long, we only check suffixes of length 1 through 200 (or the buffer length, whichever is smaller). Any suffix longer than the longest word cannot match a word, so checking past maxLen is wasted work. For each suffix we build the substring and look it up in the HashSet.

Algorithm

  1. Store all words in a HashSet. Track maxLen, the length of the longest word.
  2. Maintain a list (or StringBuilder) called stream that accumulates all queried characters.
  3. For each query(letter):
    • Append letter to stream.
    • Check suffixes of stream from length 1 up to min(maxLen, stream.length).
    • If any suffix is found in the HashSet, return true.
    • If no suffix matches, return false.

Visualization and Code

Loading animation...

The bottleneck is substring creation. Each query builds up to 200 substrings, copying characters every time. The next approach walks through the characters once, sharing one traversal across all suffix lengths.

Approach 2: Trie with Reversed Words (Optimal)

Intuition

A suffix of the stream ends at the current position and extends backward. If we reverse every word and insert the reversed forms into a Trie, then checking suffixes becomes a forward traversal of that Trie, starting from the most recent character and moving backward through the stream.

For example, the word "cd" reverses to "dc", and we insert "dc" into the Trie. When the stream is "abcd", we start from 'd' (the latest character), then move to 'c'. In the Trie we follow d -> c, and since "dc" is marked as a complete word, "cd" is a suffix of the stream.

Per query we traverse at most maxLen characters backward, and the Trie tests all words in one pass. No substring creation, no hashing.

Algorithm

  1. Build a Trie from all words, but insert each word in reverse. Mark the end of each reversed word.
  2. Track maxLen, the longest word length.
  3. Maintain a list stream of all queried characters.
  4. For each query(letter):
    • Append letter to stream.
    • Start at the Trie root. Walk backward through stream from the latest character.
    • At each step, follow the corresponding child in the Trie. If the child does not exist, return false.
    • If we reach a node marked as a word end, return true.
    • Stop after checking maxLen characters or exhausting the stream.
    • If no match found, return false.

Visualization and Code

Loading animation...