Stream of Characters - Practice Coding Problems

Stream of Characters - Problem

Array String Design Trie Data Stream Hard

Design an algorithm that accepts a stream of characters and checks if a suffix of these characters is a string from 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.

Input & Output

Example 1 — Basic Stream Processing

$ Input: words = ["cd", "f", "kl"], queries = "abcdefg"

› Output: [false, false, false, true, false, true, false]

💡 Note: Stream builds as 'a', 'ab', 'abc', 'abcd' (suffix 'cd' matches), 'abcde', 'abcdef' (suffix 'f' matches), 'abcdefg'

Example 2 — Multiple Matches

$ Input: words = ["ab", "ba", "aaab"], queries = "aaba"

› Output: [false, false, true, true]

💡 Note: Stream: 'a' → 'aa' → 'aab' (suffix 'ab' matches) → 'aaba' (suffix 'ba' matches)

Example 3 — No Matches

$ Input: words = ["xyz"], queries = "abc"

› Output: [false, false, false]

💡 Note: Stream 'a' → 'ab' → 'abc' never forms suffix 'xyz'

Constraints

1 ≤ words.length ≤ 2000
1 ≤ words[i].length ≤ 2000
words[i] consists of lowercase English letters
At most 4 × 10⁴ calls to query

Visualization

Tap to expand

Understanding the Visualization

Input

Words array ["cd", "f"] and character stream

Process

Build data structure and process each character

Output

Boolean array indicating suffix matches

Key Takeaway

🎯 Key Insight: Reverse trie enables O(L) suffix matching per character instead of O(n²) brute force

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Facebook 18

The key insight is to use a reverse trie data structure that stores words backwards, enabling efficient suffix matching. Instead of checking all possible suffixes, we traverse the trie from the most recent character backwards. Best approach uses reverse trie with Time: O(n × L), Space: O(M × L).

Common Approaches

Approach	Time	Space	Notes
✓ Reverse Trie (Optimal)	O(n × L)	O(M × L)	Build trie with reversed words and match suffixes efficiently
Brute Force String Matching	O(n²)	O(n + m)	Store stream and check all possible suffixes against all words

Reverse Trie (Optimal) — Algorithm Steps

Build trie with all words reversed
For each query, try to match from all possible starting positions
Use trie traversal to detect word endings

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Trie

Create trie with reversed words

Add Character

Append to stream and traverse trie backwards

Check Match

Detect word ending during traversal

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_CHILDREN 26
#define MAX_LEN 2000

typedef struct TrieNode {
    struct TrieNode* children[MAX_CHILDREN];
    bool isWord;
} TrieNode;

TrieNode* createNode() {
    TrieNode* node = malloc(sizeof(TrieNode));
    for (int i = 0; i < MAX_CHILDREN; i++) {
        node->children[i] = NULL;
    }
    node->isWord = false;
    return node;
}

typedef struct {
    TrieNode* root;
    char stream[MAX_LEN];
    int streamLen;
} StreamChecker;

StreamChecker* createStreamChecker(char words[][MAX_LEN], int wordCount) {
    StreamChecker* sc = malloc(sizeof(StreamChecker));
    sc->root = createNode();
    sc->streamLen = 0;
    
    // Build trie with reversed words
    for (int i = 0; i < wordCount; i++) {
        TrieNode* node = sc->root;
        int len = strlen(words[i]);
        for (int j = len - 1; j >= 0; j--) {
            int idx = words[i][j] - 'a';
            if (!node->children[idx]) {
                node->children[idx] = createNode();
            }
            node = node->children[idx];
        }
        node->isWord = true;
    }
    
    return sc;
}

bool query(StreamChecker* sc, char letter) {
    sc->stream[sc->streamLen++] = letter;
    
    TrieNode* node = sc->root;
    for (int i = sc->streamLen - 1; i >= 0; i--) {
        int idx = sc->stream[i] - 'a';
        if (!node->children[idx]) {
            break;
        }
        node = node->children[idx];
        if (node->isWord) {
            return true;
        }
    }
    return false;
}

int main() {
    char words[1000][MAX_LEN];
    char line[MAX_LEN];
    
    fgets(line, sizeof(line), stdin);
    int wordCount = 0;
    char* token = strtok(line, "[],\"");
    while (token != NULL && wordCount < 1000) {
        if (strlen(token) > 0 && token[0] != ' ' && token[0] != '\n') {
            strcpy(words[wordCount++], token);
        }
        token = strtok(NULL, "[],\"");
    }
    
    fgets(line, sizeof(line), stdin);
    char queries[MAX_LEN] = "";
    for (int i = 0; line[i]; i++) {
        if (line[i] >= 'a' && line[i] <= 'z') {
            strncat(queries, &line[i], 1);
        }
    }
    
    StreamChecker* sc = createStreamChecker(words, wordCount);
    printf("[");
    for (int i = 0; queries[i]; i++) {
        bool result = query(sc, queries[i]);
        printf(result ? "true" : "false");
        if (queries[i+1]) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × L)

For n queries, each takes O(L) where L is max word length

✓ Linear Growth

Space Complexity

O(M × L)

Trie stores M words with average length L, plus tracking state

✓ Linear Space

89.2K Views

Medium Frequency

~35 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Reverse Trie (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler