Pattern visualizer

First Non-Repeating Character in a Stream

Re-scanning everything seen so far after each character is the obvious answer and it is quadratic. The insight is that 'first' means oldest, and a queue already stores things oldest-first — so the answer is never searched for, it is just the front. A character joins the back when it arrives; once its count passes one it is dead, but deleting it from the middle would cost a scan, so it is left in place and simply thrown away if it ever reaches the front. Every character is therefore pushed once and popped at most once, and each answer is a single peek. Animated on: stream = "aabcbd" — after every character, report the first character so far that has appeared exactly once, or '#' if there is none. The row drawn is the QUEUE of surviving candidates, not the stream..

The queue keeps candidates in arrival order, so the answer is always the front

time O(n) total — each character is pushed once and popped at most oncespace O(k) for the queue and the counts, k = alphabet sizestep 1 / 13

[0]

line 6

'a' arrives and is brand new, so it joins the BACK of the queue as the newest candidate. The queue is now [a] — every character still in the running, in the order it showed up, which is exactly the order the answer has to be picked in.

Pseudocode

1FUNCTION firstNonRepeating(stream)
2  queue <- empty queue
3  count <- empty map
4  FOR EACH ch IN stream
5    count[ch] <- count[ch] + 1
6    ENQUEUE ch INTO queue
7    WHILE queue IS NOT EMPTY AND count[FRONT(queue)] > 1
8      DEQUEUE FROM queue
9    IF queue IS EMPTY
10      OUTPUT '#'
11    ELSE
12      OUTPUT FRONT(queue)

← / → step · space play · Home restart

Where to practice Queue

Practice Queue problems All Queue problems Back to roadmap