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) =
aabcReturns (string)
a#bbExample 2
Input
stream (string) =
abcReturns (string)
aaaExample 3
Input
stream (string) =
zzReturns (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 resultReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run