# Queue based approach for first non-repeating character in a stream

Difficulty Level Medium
Frequently asked in Amazon Flipkart Microsoft PayU Yahoo

## Problem Statement

The problem “Queue based approach for first non-repeating character in a stream” states that you are given a stream containing lower case characters, find the first non-repeating character whenever a new character is added to the stream, and if there is no non-repeating character return -1.

## Examples

`aabcddbe`
`a -1 b b b b c c`

Explanation: As we can see that output has the first non-repeating character everywhere except the second index. But until index 2 all characters have been repeated. So, -1 is printed at index 2.

`abcdabcd`
`a a a a b c d -1` ## Algorithm for First non-repeating character in a stream

The above problem can be solved using a queue. So, we only need to maintain a queue of characters, and an array of frequency. The array stores the frequency of every character in the stream.
Thus for every character in the stream. And then increase the frequency of that character and push it to the queue. Check the character at the starting of the queue, if the frequency of that character is 1, return the character. Else, pop out the character, and check for next character. If the queue becomes empty, return -1 and continue to process other characters in the stream.

1. Create a queue of characters and an array that stores the frequency of every character.
2. One by one process the inputs of the stream.
3. For current character input in stream, increase the frequency and push it to the queue.
4. Check the character at front of queue, if the frequency of that character is 1, print the character, else remove the first character in the queue and repeat step 4.
5. If queue becomes empty during step 4, print -1 and continue to process next character.

## Complexity Analysis for First non-repeating character in a stream

Since we have traversed the stream exactly once and every character might be pushed to the queue and removed from the queue exactly once. So
Time Complexity = O(n)
Space Complexity = O(n)
where n is the total number of characters in the stream.

## Code

### Java Code for First non-repeating character in a stream

```import java.util.LinkedList;
import java.util.Queue;

class QueueBasedApproachForFirstNonRepeatingCharacterInAStream {
private static void firstNonRepeatingCharacter(String stream) {
// create a array to store frequency of characters
int freq[] = new int;
// create a queue

// traverse the stream character by character
for (int i = 0; i < stream.length(); i++) {
// current character of stream
char curr = stream.charAt(i);
// increase the frequency
freq[curr - 'a']++;
// push it to queue

while (!queue.isEmpty()) {
// check the frequency of first character in queue
char front = queue.peek();
if (freq[front - 'a'] == 1) {
// if freq is 1, print the first character
System.out.print(front + " ");
break;
} else {
// else remove the first character
queue.poll();
}
}

// if queue becomes empty, print -1
if (queue.isEmpty()) {
System.out.print("-1 ");
}
}
System.out.println();
}

public static void main(String[] args) {
// Example 1
String stream1 = "aabcddbe";
firstNonRepeatingCharacter(stream1);

// Example 2
String stream2 = "abcdabcd";
firstNonRepeatingCharacter(stream2);
}
}```
```a -1 b b b b c c
a a a a b c d -1```

### C++ Code for First non-repeating character in a stream

```#include<bits/stdc++.h>
using namespace std;

void firstNonRepeatingCharacter(string stream) {
// create a array to store frequency of characters
int freq;
for (int i = 0; i < 26; i++) {
freq[i] = 0;
}
// create a queue
queue<char> q;

// traverse the stream character by character
for (int i = 0; i < stream.length(); i++) {
// current character of stream
char c = stream[i];
// increase the frequency
freq[c - 'a']++;
// push it to queue
q.push(c);

while (!q.empty()) {
// check the frequency of first character in queue
char front = q.front();
if (freq[front - 'a'] == 1) {
// if freq is 1, print the first character
cout<<front<<" ";
break;
} else {
// else remove the first character
q.pop();
}
}

// if queue becomes empty, print -1
if (q.size() == 0) {
cout<<"-1 ";
}
}
cout<<endl;
}

int main() {
// Example 1
string stream1 = "aabcddbe";
firstNonRepeatingCharacter(stream1);

// Example 2
string stream2 = "abcdabcd";
firstNonRepeatingCharacter(stream2);

return 0;
}```
```a -1 b b b b c c
a a a a b c d -1```
Translate »