7

First Non-Repeating Character In A Running Stream in C++

 2 years ago
source link: https://www.journaldev.com/61277/first-non-repeating-character-running-stream-c
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

In today’s article, we will learn to solve the problem to find the first non-repeating character in a running stream of input. It is a super important question if you’re appearing for an interview. I would never recommend you to skip this problem. Questions like this are a strong example to practice the data structures and algorithms. So without wasting any time, let’s quickly head toward the problem statement.

Problem Statement to Find the First Non-Repeating Character

You have a running stream of input, your task is to find the first non-repeating character out of this sequence at every step. And print -1 in case there is none.

For example,

Input Stream:     a b b a c
Output Stream:    a a a -1 c
Input Stream:     a c d a g e g t g h s g j
Output Stream:    a a a c c c c c c c c c c
Input Stream:     d g d f d d d d f f f s a a a s g s s g g t
Output Stream:    d d g g g g g g g g g g g g g g d d d d d d

Concept of Searching for First Non-Repeating Character

To tackle this problem, we are going to use a multi-conceptual approach. We will use a hash map in combination with a queue. The hash map will store a mapping between the input characters and the queue will store the input characters. Below is the detailed logic that we will follow while writing the algorithm.

  • First, create a mapping between the input characters and their frequency.
  • At the same time, keep pushing the input in a queue of characters.
  • This queue will help us to generate the output, as it works on FIFO(First In, First Out) property.
  • We will perform all the logic during the input itself because we have to work on a running stream of input.
  • So, as soon as you input an element, it’s time to output the corresponding first non-repeating character.
  • Check the queue, if it’s empty, print -1.
  • Otherwise, extract the element at the front of the queue.
    • If the frequency of this element is one, print it.
    • Otherwise, pop it out of the queue.

Algorithm to Search for First Non-Repeating Character

while(true)
{
char ch;
cin >> ch;
if(ch == '!')
break;
// logic begins here
output_stream.push(ch);
if(freq_table.find(ch) != freq_table.end())
freq_table[ch] += 1;
else
freq_table.insert(make_pair(ch, 1));
// time to display the result
while(!output_stream.empty())
{
char front_ele = output_stream.front();
if(freq_table[front_ele] != 1)
{
output_stream.pop();
}
else
{
cout << front_ele << " ";
break;
}
}
if(output_stream.empty())
cout << "-1 ";
}

Program To Find The First Non-Repeating Character in A Running Stream

Let’s now look at how we can implement the above algorithm in a C++ program with ease.

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
int main()
{
cout << "Enter the input, press ! to stop" << endl;
unordered_map <char, int> freq_table;
queue <char> output_stream;
while(true)
{
char ch;
cin >> ch;
if(ch == '!')
break;
// logic begins here
output_stream.push(ch);
if(freq_table.find(ch) != freq_table.end())
freq_table[ch] += 1;
else
freq_table.insert(make_pair(ch, 1));
// time to display the result
while(!output_stream.empty())
{
char front_ele = output_stream.front();
if(freq_table[front_ele] != 1)
{
output_stream.pop();
}
else
{
cout << front_ele << " ";
break;
}
}
if(output_stream.empty())
cout << "-1 ";
}
cout << endl;
return 0;
}
First Non Repeating Characters AlgorithmFirst Non-Repeating Characters Algorithm

Output

First Non Repeating Character OutputFirst Non-Repeating Character Output

Space And Time Complexity Analysis

As you can notice, we are using two extra data structures to store the input data and process it. This implies that for the queue we need O(N) amount of extra space and the same goes for the unordered map.

During each input, we are doing a linear amount of work. This means we are iterating over the queue every time we receive input. It implies that the overall time complexity is going to be O(N2).

Conclusion

In this article, we learned to find the first non-repeating character in a running stream of input. The idea to use a queue is simple and effective. The code is moderately tough to implement, that’s a perfect example of the applications of queues in the real world. That’s all for today, thanks for reading.

Further Readings

To learn more about queues and recursion, you can visit the following articles.

https://www.journaldev.com/56532/queue-class-in-cpp

https://www.journaldev.com/61078/reverse-a-stack-cpp


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK