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

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[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