To find the first non-repeating character in a stream efficiently, the key is to process characters in real time while keeping track of both frequency and order.

The idea

You need two things working together:

1. A way to count how many times each character appears

2. A way to remember the order in which characters arrived

Efficient approach

Use:

• A hash map (dictionary) → to store frequency of each character

• A queue → to track characters in the order they appear

How it works step by step

For every incoming character in the stream:

1. Increase its count in the hash map

2. Add it to the queue

3. While the front of the queue has frequency > 1, remove it

4. The front of the queue (if any) is your answer

Example

Stream: a a b c b

• After a → first non-repeating = a

• After second a → none

• After b → b

• After c → b

• After second b → c

Python implementation

from collections import deque

def first_non_repeating(stream):
    freq = {}
    q = deque()
    
    result = []
    
    for ch in stream:
        freq[ch] = freq.get(ch, 0) + 1
        q.append(ch)
        
        while q and freq[q[0]] > 1:
            q.popleft()
        
        result.append(q[0] if q else None)
    
    return result

Complexity

• Time: O(n)

• Space: O(k), where k is number of unique characters

Why this works well

• You process each character only once

• You never re-scan the stream

• You always have the answer ready in constant time

Real-world relevance

This pattern is useful in:

• Real-time log processing

• Streaming data pipelines

• Event-driven systems

If you’re building systems that deal with continuous data, this kind of approach becomes extremely powerful.