# Stream of Characters
**Difficulty:** HARD
[External](https://leetcode.com/problems/stream-of-characters)
Canonical: https://scaleengineer.com/dsa/problems/stream-of-characters
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design), [Data Stream](https://scaleengineer.com/dsa/patterns/data-stream)
**Data structures:** Array, String, Trie
**Companies:** [Salesforce](https://scaleengineer.com/companies/salesforce), [Jane Street](https://scaleengineer.com/companies/jane-street)
---
## 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 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 <= 2000`
* `1 <= words[i].length <= 200`
* `words[i]` consists of lowercase English letters.
* `letter` is a lowercase English letter.
* At most `4 * 104` calls will be made to query.

# Approaches
## Brute Force Suffix Matching
This is a straightforward, brute-force approach. We maintain the history of the character stream. For each new character queried, we append it to our stream history. Then, we generate all possible suffixes of the current stream (up to the maximum possible word length) and check if any of them exist in the given `words` list.
**Time:** Constructor: O(W), where W is the total number of characters in `words`. `query(char letter)`: O(L^2), where L is the maximum length of a word. For each query, we might check up to L suffixes. Each suffix operation (substring creation and hash lookup) can take O(L) time. · **Space:** O(W) + O(Q), where W is the total number of characters in all words (for the `wordSet`) and Q is the number of queries (for the `streamHistory`). The space for the stream can be optimized to O(L) by only storing the last L characters, where L is the maximum word length.
**Pros:** Simple to understand and implement.
**Cons:** Highly inefficient for each query, likely to result in a 'Time Limit Exceeded' error for large inputs.; The process of repeatedly creating substrings and performing hash lookups for each query is computationally expensive.
### Explanation
In the `StreamChecker` constructor, we convert the input `words` array into a `HashSet` for efficient O(1) average time lookups. We also pre-calculate the maximum length of any word in the dictionary to avoid checking unnecessarily long suffixes. A `StringBuilder` is used to store the characters from the stream.

In the `query(char letter)` method, we first append the new `letter` to our `StringBuilder`. Then, we iterate backwards from the end of the stream, forming a new suffix in each step. For each suffix, we check for its existence in the `HashSet` of words. If a match is found, we immediately return `true`. If we check all possible suffixes (with length up to `maxWordLength`) and find no match, we return `false`.

```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class StreamChecker {
    private Set<String> wordSet;
    private StringBuilder streamHistory;
    private int maxWordLength;

    public StreamChecker(String[] words) {
        wordSet = new HashSet<>(Arrays.asList(words));
        streamHistory = new StringBuilder();
        maxWordLength = 0;
        for (String word : words) {
            maxWordLength = Math.max(maxWordLength, word.length());
        }
    }

    public boolean query(char letter) {
        streamHistory.append(letter);
        // We only need to check suffixes up to maxWordLength
        for (int i = streamHistory.length() - 1; i >= 0 && streamHistory.length() - i <= maxWordLength; i--) {
            String suffix = streamHistory.substring(i);
            if (wordSet.contains(suffix)) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- In the `StreamChecker` constructor, convert the `words` array into a `HashSet` for fast lookups. Also, find the maximum length (`maxWordLength`) of any word in the list.
- Maintain a `StringBuilder`, `streamHistory`, to keep track of the characters received.
- For each `query(letter)` call:
  1. Append the new `letter` to `streamHistory`.
  2. Iterate backwards from the end of `streamHistory`.
  3. In each iteration, extract a suffix.
  4. Limit the check to suffixes with length up to `maxWordLength`.
  5. For each extracted suffix, check if it exists in the `wordSet`.
  6. If a match is found, return `true` immediately.
  7. If the loop completes without finding any matching suffix, return `false`.

## Optimized Suffix Matching with a Reversed Trie
This approach significantly optimizes the query time by using a Trie (prefix tree). The key insight is to rephrase the problem of matching suffixes of a stream into matching prefixes of a reversed stream. We achieve this by building a Trie from the **reversed** words of the input dictionary.
**Time:** Constructor: O(W), where W is the total number of characters in `words`. `query(char letter)`: O(L), where L is the maximum length of a word. The backward traversal in the Trie is bounded by its maximum depth, which is L. · **Space:** O(W) + O(Q), where W is the total number of characters in `words` for storing the Trie, and Q is the number of queries for storing the `streamHistory`. The stream space can be optimized to O(L) by using a fixed-size `Deque` or by trimming the `StringBuilder`.
**Pros:** Extremely efficient query time, making it ideal for a large number of queries.; The one-time preprocessing cost of building the Trie is amortized over all subsequent queries.; This is a standard and elegant solution for this category of suffix/prefix matching problems.
**Cons:** More complex to implement compared to the brute-force approach.; Requires additional space for the Trie data structure.; Stores a history of the stream, which consumes memory (though this can be bounded).
### Explanation
First, we design a `TrieNode` class. In the `StreamChecker` constructor, we build a Trie by inserting every word from the input array in reverse order. For example, if `words` contains `"abc"`, we insert `"cba"` into the Trie. We mark the node corresponding to the last character of the inserted reversed word (i.e., the node for `'a'`) to indicate that it forms a complete word.

For each `query(char letter)`, we append the new character to our stream history (e.g., a `StringBuilder`). Then, we traverse this history backwards, starting from the newest character, and simultaneously traverse our Trie from the root. If we can trace a path in the Trie that corresponds to a reversed word, it means the current suffix of our stream matches a word in the dictionary. For instance, if the stream is `"...xya"` and we have `"abc"` in our dictionary (stored as `"cba"` in the Trie), when we query `'b'` and then `'c'`, the backward traversal `c -> b -> a` will find a match in the Trie.

The backward traversal is naturally bounded by the maximum depth of the Trie, which is the length of the longest word, making each query very fast.

```java
class StreamChecker {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isWord = false;
    }

    private final TrieNode root;
    private final StringBuilder streamHistory;

    public StreamChecker(String[] words) {
        root = new TrieNode();
        streamHistory = new StringBuilder();
        
        for (String word : words) {
            TrieNode curr = root;
            // Insert word in reverse order
            for (int i = word.length() - 1; i >= 0; i--) {
                int index = word.charAt(i) - 'a';
                if (curr.children[index] == null) {
                    curr.children[index] = new TrieNode();
                }
                curr = curr.children[index];
            }
            curr.isWord = true;
        }
    }

    public boolean query(char letter) {
        streamHistory.append(letter);
        TrieNode curr = root;
        // Traverse backwards from the end of the stream.
        // The loop is implicitly bounded by the max depth of the Trie (max word length),
        // because if a path doesn't exist, curr becomes null and the loop terminates.
        for (int i = streamHistory.length() - 1; i >= 0; i--) {
            int index = streamHistory.charAt(i) - 'a';
            if (curr.children[index] == null) {
                return false;
            }
            curr = curr.children[index];
            if (curr.isWord) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- Define a `TrieNode` class with a `children` array (for each letter) and an `isWord` boolean flag.
- In the `StreamChecker` constructor:
  1. Initialize a `TrieNode root`.
  2. For each `word` in the input `words` array, insert its **reversed** version into the Trie. Mark the node corresponding to the end of the reversed word by setting `isWord = true`.
  3. Initialize a `StringBuilder streamHistory` to store the stream.
- For each `query(letter)` call:
  1. Append the `letter` to `streamHistory`.
  2. Start a traversal from the `root` of the Trie.
  3. Iterate backwards through `streamHistory`, starting from the last character.
  4. For each character, move down the Trie. If a path does not exist (`null` child), it means no word can be formed, so break and return `false`.
  5. If at any point the traversal reaches a node where `isWord` is `true`, a valid suffix has been found, so return `true`.
  6. If the backward traversal completes without finding a word, return `false`.

# Solutions
### Java

```java
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); */
```

### CPP

```cpp
class Trie { public: vector < Trie *> children ; bool isEnd ; Trie () : children ( 26 ) , isEnd ( false ) {} void insert ( string & w ) { Trie * node = this ; reverse ( w . begin (), w . end ()); for ( char & c : w ) { int idx = c - 'a' ; if ( ! node -> children [ idx ]) { node -> children [ idx ] = new Trie (); } node = node -> children [ idx ]; } node -> isEnd = true ; } bool search ( string & w ) { Trie * node = this ; for ( int i = w . size () - 1 ; ~ i ; -- i ) { int idx = w [ i ] - 'a' ; if ( ! node -> children [ idx ]) { return false ; } node = node -> children [ idx ]; if ( node -> isEnd ) { return true ; } } return false ; } }; class StreamChecker { public: Trie * trie = new Trie (); string s ; StreamChecker ( vector < string >& words ) { for ( auto && w : words ) { trie -> insert ( w ); } } bool query ( char letter ) { s += letter ; return trie -> search ( s ); } }; /** * Your StreamChecker object will be instantiated and called as such: * StreamChecker* obj = new StreamChecker(words); * bool param_1 = obj->query(letter); */
```

### Python

```python
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)
```