Queue Deque Simulation
Intermediate Level

Implement the firstNonRepeatingCharacterStream method that returns the first non-repeating character after processing a stream.

The input contains a string stream. Characters arrive one by one from left to right.

After reading each character, your task is to append the first character that has appeared exactly once so far. If there is no non-repeating character at that moment, append #.

For example, for aabc, the result is a#bb.

Example 1
Input:
stream (string) = aabc
Return:
(string) a#bb
Example 2
Input:
stream (string) = abc
Return:
(string) aaa
Example 3
Input:
stream (string) = zz
Return:
(string) z#

Use a frequency map and a queue.

For each new character, increase its frequency and add it to the queue. Then remove characters from the front of the queue while their frequency is greater than one.

If the queue is not empty, its front is the first non-repeating character. If the queue is empty, append #.

Pseudocode:

function firstNonRepeatingCharacterStream(stream):
    frequency = empty map
    queue = empty queue
    result = empty string
    for each character ch in stream:
        frequency[ch]++
        push ch into queue
        while queue is not empty and frequency[front(queue)] > 1:
            pop front from queue
        if queue is empty:
            append '#' to result
        else:
            append front(queue) to result
    return result
Run your code to see the result.