Queue: Find the first non repeating character in the stream

Problem Statement:

You are given a stream of characters you need to find the first non repeating character every time when a character is inserted into the stream.

You can return -1, if no character is present.

Example:

Input: a[] = a a b 

Output: a -1 b

Solution Explanation:

We will use frequency array and queue to solve the problem.

Create a array of size 26 and for each char in the string push the element into the queue and increment the frequency array.

Then for each char in the stream, check the frequency of the element in front of the queue.

If it is one, then it is the first non repeating element, if not pop the element.

If the queue becomes empty, means, there are no non repeating character and print -1

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;


void solution(char str[])
{
    queue<char> q;
    int freqArray[26] = { 0 };

    // traverse stream char one by one
    for (int i = 0; str[i]; i++) 
    {

        q.push(str[i]);

        freqArray[str[i] - 'a']++;

        while (!q.empty()) 
        {
            if (freqArray[q.front() - 'a'] > 1)
                q.pop();
            else 
            {
                cout << q.front() << " ";
                break;
            }
        }

        if (q.empty())
            cout << -1 << " ";
    }
    cout << endl;
}

int main()
{
    char str[] = "aab";

    solution(str);
    
    return 0;
}

Output

a -1 b