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

Difficulty Level Medium
Frequently asked in Amazon Flipkart Microsoft PayU Yahoo
Hash Linked-List Queue String

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

 

Queue based approach for first non-repeating character in a streamPin

Please click Like if you loved this article?

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.
See also
Merge Sorted Array

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[26];
        // create a queue
        Queue<Character> queue = new LinkedList<>();

        // 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
            queue.add(curr);

            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[26];
    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
Please click Like if you loved this article?