First Non-Repeating Character in a Stream

Given a stream of characters, find the first non-repeating character at any point. If all characters have repeated, return a sentinel like '#'.

Example

Stream: a, a, b, c, b, d
After a: a (first non-repeating)
After a: # (a repeated)
After b: b
After c: b
After b: c (b repeated, c is first non-repeating)
After d: c

Solution — Queue + Frequency Map

from collections import deque

class FirstNonRepeating:
    def __init__(self):
        self.queue = deque()
        self.freq = {}
    
    def add(self, char):
        """
        Add character and return first non-repeating.
        Time: O(1) amortized per call
        """
        self.freq[char] = self.freq.get(char, 0) + 1
        self.queue.append(char)

        # Drain repeated characters from front
        while self.queue and self.freq[self.queue[0]] > 1:
            self.queue.popleft()

        return self.queue[0] if self.queue else '#'

Trace

char | freq            | queue    | drain      | result
-----|-----------------|----------|------------|-------
a    | {a:1}           | [a]      | —          | a
a    | {a:2}           | [a]      | pop a → [] | #
b    | {a:2,b:1}       | [b]      | —          | b
c    | {a:2,b:1,c:1}   | [b,c]    | —          | b
b    | {a:2,b:2,c:1}   | [b,c]    | pop b→[c]  | c
d    | {a:2,b:2,c:1,d:1}| [c,d]   | —          | c

Why Queue?

Characters that arrived earlier should be checked first for non-repeating status. A queue’s FIFO order naturally maintains this — the front is always the oldest candidate.

Batch Processing Version

Process the entire stream and return the first non-repeating at each step:

def first_non_repeating_all(stream):
    """Return first non-repeating char after each addition."""
    queue = deque()
    freq = {}
    results = []

    for char in stream:
        freq[char] = freq.get(char, 0) + 1
        queue.append(char)

        while queue and freq[queue[0]] > 1:
            queue.popleft()

        results.append(queue[0] if queue else '#')

    return results

Complexity

Each character enters the queue once and leaves once → O(2n) total operations across all calls.

Edge Cases

• All unique characters — front of queue is always the answer
• All same character — always returns '#' after second occurrence
• Single character stream — returns that character
• Large alphabet — works for any hashable characters

When to Use This Pattern

• Real-time log analysis (first unique event)
• Network packet deduplication
• Streaming data analytics
• Any “first unique in window” variant

Related Problems

• First Unique Character in a String (LeetCode 387) — static version
• Moving Average from Data Stream (LeetCode 346)
• Design Hit Counter (LeetCode 362)