First Non Repeating Character in a Stream

Task: Find the first non repeating character in a stream, The steam is inserted one character at a time from given string. Print first non repeating character in every inserting time if no such character exist print -1.

Example:

Input:

1

3

a a c

Output:

a -1 c

---

Here is the Code:

Program in C++:

1. #include<iostream>
2. #include<bits/stdc++.h>
3. using namespace std;
4. map<char,int> m;
5. queue<char> q;
6. void fnrcInStream(char *a,int n)
7. {
8.     for(int i=0;i<n;i++)
9.     {
10.         if(m.find(a[i])==m.end())
11.         {
12.             q.push(a[i]);
13.         }
14.         m[a[i]]++;
15.         if(m[q.front()]==1)
16.         {
17.             cout<<q.front()<<" ";
18.         }
19.         else
20.         {
21.             while(!q.empty())
22.             {
23.                 q.pop();
24.                 if(m[q.front()]==1)
25.                 {
26.                     cout<<q.front()<<" ";
27.                     break;
28.                 }
29.             }
30.             if(q.empty())
31.             {
32.                 cout<<-1<<" ";
33.             }
34.         }
35.     }
36.     while(!q.empty())
37.     {
38.         q.pop();
39.     }
40.     m.clear();
41.     cout<<endl;
42. }
43. int main()
44.  {
45. int t;
46. cin>>t;
47. while(t--)
48. {
49.     int n;
50.     cin>>n;
51.     char a[n];
52.     for(int i=0;i<n;i++)
53.     {
54.         cin>>a[i];
55.     }
56.     fnrcInStream(a,n);
57. }
58. return 0;
59. }

---

Here is the Video: