You must design a data structure that supports:

StreamChecker(String[] words)
query(char letter) → returns true if any word in words is a suffix
                      of the streamed characters so far

Meaning:

• Characters arrive one by one
• After each query, you check whether the sequence of characters seen so far ends with any word from the given list
• Return true if at least one word matches as a suffix, else false

Example:

Input:
words = ["cd","f","kl"]
Queries and output:
query('a') → false
query('b') → false
query('c') → false
query('d') → true   (stream ends with "cd")
query('k') → false
query('l') → true   (stream ends with "kl")

---

Problem Understanding

Key observations:

• You do not search for substrings anywhere — only suffix matches
• Stream keeps growing, but you only care about latest characters
• Matching must be efficient because:
  • up to 2000 words
  • each up to length 2000
  • up to 40,000 queries

Brute force checking becomes far too slow.

So we need a smarter way to detect whether the ending of the current stream matches any word.

---

Logic Explained in Simple English

The fastest method relies on a key insight:

Instead of storing words normally, store them reversed in a Trie.

Why?

• The query asks whether the end of the stream matches any word
• If we reverse all words, then matching suffixes becomes matching prefixes
• When new characters arrive, we check from newest backward

So:

1. Reverse each word and insert into a Trie
2. Maintain a running character stream (as a StringBuilder or list)
3. On each query:
   • append new character
   • walk the Trie using stream characters in reverse order
   • if we reach a terminal Trie node → return true
   • if we hit a null child → return false

Also important:

We do not need to store the entire stream forever.

Why?

• Only the last maxWordLength characters can ever matter
• Anything earlier cannot form a suffix match

So after appending, we can trim length if needed.

---

Step-by-Step Approach

Step 1: Build reversed Trie

• Each node has up to 26 children (lowercase letters)
• A boolean flag marks the end of a valid word

Step 2: Track stream characters

• Use a StringBuilder or deque
• Append each new query character to the end
• If stream length exceeds max word length, drop earliest characters

Step 3: Query processing

1. Add character to stream
2. Starting from end of stream, walk down Trie:
   • If child missing → return false
   • If we hit an end-of-word flag → return true
3. If traversal ends without match → return false

---

Java Implementation

class StreamChecker {

    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isWord;
    }

    private TrieNode root;
    private StringBuilder stream;
    private int maxLen;

    public StreamChecker(String[] words) {
        root = new TrieNode();
        stream = new StringBuilder();
        maxLen = 0;

        for (String w : words) {
            maxLen = Math.max(maxLen, w.length());
            insertReversed(w);
        }
    }

    private void insertReversed(String word) {
        TrieNode curr = root;
        for (int i = word.length() - 1; i >= 0; i--) {
            int idx = word.charAt(i) - 'a';
            if (curr.children[idx] == null) {
                curr.children[idx] = new TrieNode();
            }
            curr = curr.children[idx];
        }
        curr.isWord = true;
    }

    public boolean query(char letter) {
        stream.append(letter);
        if (stream.length() > maxLen) {
            stream.deleteCharAt(0);
        }

        TrieNode curr = root;
        for (int i = stream.length() - 1; i >= 0; i--) {
            int idx = stream.charAt(i) - 'a';
            if (curr.children[idx] == null) {
                return false;
            }
            curr = curr.children[idx];
            if (curr.isWord) {
                return true;
            }
        }
        return false;
    }
}

---

Dry Run Example

Words:

["cd","f","kl"]

Reversed insertion:

"dc"
"f"
"lk"

maxLen = 2

Queries:
Stream starts empty

1. query(‘a’):
   stream = “a”
   check reverse: ‘a’ → no match
   return false
2. query(‘b’):
   stream = “ab”
   check ‘b’ → no child
   return false
3. query(‘c’):
   stream = “bc”
   check ‘c’ → child exists (part of “cd”)
   next char: ‘b’ → no continuation
   return false
4. query(‘d’):
   stream = “cd” (maxLen)
   check ‘d’ → child exists
   next char: ‘c’ → completes “cd” word
   return true
5. query(‘k’):
   stream = “dk”
   check ‘k’ → child exists (part of “kl”)
   next char: ‘d’ → no continuation
   return false
6. query(‘l’):
   stream = “kl”
   check ‘l’ → child exists
   next: ‘k’ → completes “kl”
   return true

---

Time and Space Complexity

Time Complexity

For each query:

O(min(streamLength, maxLen)) → worst O(maxLen)

Since maxLen ≤ 2000, queries are efficient.

Space Complexity

O(sum of word lengths)

Trie stores reversed words

---

Common Mistakes and How to Avoid Them

Mistake 1: Checking entire stream every time

Only last max-length matters

Mistake 2: Using normal Trie

Suffix matching becomes inefficient — must reverse

Mistake 3: Scanning words instead of Trie traversal

Too slow for repeated queries

Mistake 4: Building full stream indefinitely

Memory grows unnecessarily

Mistake 5: Returning early on first mismatch

Must detect isWord inside traversal