First non-repeating character in a stream of characters(interviewbit.com)
From the website called interviewbit.com, I find an interesting problem called “First non-repeating character in a stream of characters”, by doing some research on this problem, I will provide a queue-based solution with time complexity O(n).
Problem Description:
Given a string A denoting a stream of lowercase alphabets. You have to make a new string B.
B is formed such that we have to find the first non-repeating character each time a character is inserted into the stream and append it at the end to B. If no non-repeating character is found then append ‘#’ at the end of B.
Prerequisites:
Before diving into the solution it is important to recap what we need to know in order to solve this problem.
The queue is an abstract data structure FIFO(First In First Out ), where elements inserted first popped out first. Main operations are empty, size, front, back, push_back, pop_front.
Solution code example:
Initialize all 26 elements of the array to 0
traverse over a string
find the frequency of each character in a String A
if the number of characters in the front element of the queue is bigger than 1, then we pop. If not we push that front element into the String B.
when there are no characters left, which means no character count is less than 2, we put ‘#’
Useful links:
