Find the first non-repeating character from a stream of characters using a Count Array

Find the first non-repeating character from a stream of characters using Queue:

The idea is to maintain a count array of size 26 to keep track of the frequency of each character in the input stream. We also use a queue to store the characters in the input stream and maintain the order of their appearance.

Follow the steps below to implement above idea:

Create a count array of size 26 to store the frequency of each character.
Create a queue to store the characters in the input stream.
Initialize an empty string as the answer.
For each character in the input stream, add it to the queue and increment its frequency in the count array.
While the queue is not empty, check if the frequency of the front character in the queue is 1.
If the frequency is 1, append the character to the answer. If the frequency is greater than 1, remove the front character from the queue.
If there are no characters left in the queue, append ‘#’ to the answer.

Below is the implementation of above approach:

C++

// C++ code to implement the above approach
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
/*function to find first non-repeating character in a stream
 */
string firstNonRepeatingChar(string input_stream)
{
    // Step 1: Create a count array of size 26 to store the
    // frequency of each character.
    int count[26] = { 0 };
    // Step 2: Create a queue to store the characters in the
    // input stream.
    queue<char> q;
    // Step 3: Initialize an empty string as the answer.
    string answer = "";
 
    for (char c :
         input_stream) { // Step 4: For each character in
                         // the input stream, add it to the
                         // queue and increment its
                         // frequency in the count array.
        count++; // Increment the frequency of the
                          // character in the count array
        q.push(c); // Add the character to the queue
 
        while (!q.empty()
               && count[q.front() - 'a']
                      > 1) { // Step 5: While the queue is
                             // not empty, check if the
                             // frequency of the front
                             // character in the queue is 1.
            q.pop(); // Step 6: If the frequency is greater
                     // than 1, remove the front character
                     // from the queue.
        }
 
        if (q.empty()) { // Step 7: If there are no
                         // characters left in the queue,
                         // append '#' to the answer.
            answer += '#';
        }
        else { // Step 6: If the frequency is 1, append the
               // character to the answer.
            answer += q.front();
        }
    }
 
    return answer; // Step 8: Return the answer.
}
// Driver code
int main()
{
    string input_stream = "w3wikiandgeeksquizfor";
    string answer = firstNonRepeatingChar(input_stream);
    cout << answer << endl;
    return 0;
}
// This code is contributed by Veerendra_Singh_Rajpoot

Java

import java.util.*;
 
public class Main {
    /* Function to find first non-repeating character in a
     * stream */
    public static String
    firstNonRepeatingChar(String input_stream)
    {
        // Step 1: Create a count array of size 26 to store
        // the frequency of each character.
        int[] count = new int[26];
 
        // Step 2: Create a queue to store the characters in
        // the input stream.
        Queue<Character> q = new LinkedList<>();
 
        // Step 3: Initialize an empty string as the answer.
        String answer = "";
 
        for (char c : input_stream.toCharArray()) {
            // Step 4: For each character in the input
            // stream, add it to the queue and increment its
            // frequency in the count array.
            count++;
            q.add(c);
 
            while (!q.isEmpty()
                   && count[q.peek() - 'a'] > 1) {
                // Step 5: While the queue is not empty,
                // check if the frequency of the front
                // character in the queue is 1.
                q.remove();
            }
 
            if (q.isEmpty()) {
                // Step 7: If there are no characters left
                // in the queue, append '#' to the answer.
                answer += '#';
            }
            else {
                // Step 6: If the frequency is 1, append the
                // character to the answer.
                answer += q.peek();
            }
        }
 
        // Step 8: Return the answer.
        return answer;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String input_stream
            = "w3wikiandgeeksquizfor";
        String answer = firstNonRepeatingChar(input_stream);
        System.out.println(answer);
    }
}

Python

from collections import deque
 
 
def first_non_repeating_char(input_stream):
    # Step 1: Create a count array of size 26 to store the frequency of each character.
    count = [0] * 26
    # Step 2: Create a queue to store the characters in the input stream.
    q = deque()
    # Step 3: Initialize an empty string as the answer.
    answer = ""
 
    for c in input_stream:
        # Step 4: For each character in the input stream, add it to the queue and increment its frequency in the count array.
        count[ord(c) - ord('a')] += 1
        q.append(c)
 
        while q and count[ord(q[0]) - ord('a')] > 1:
            # Step 5: While the queue is not empty, check if the frequency of the front character in the queue is 1.
            q.popleft()
            # Step 6: If the frequency is greater than 1, remove the front character from the queue.
 
        if not q:
            # Step 7: If there are no characters left in the queue, append '#' to the answer.
            answer += '#'
        else:
            # Step 6: If the frequency is 1, append the character to the answer.
            answer += q[0]
 
    return answer  # Step 8: Return the answer.
 
 
input_stream = "w3wikiandgeeksquizfor"
answer = first_non_repeating_char(input_stream)
print(answer)

C#

using System;
using System.Collections.Generic;
 
class MainClass {
    public static string
    FirstNonRepeatingChar(string input_stream)
    {
        // Step 1: Create a count array of size 26 to store
        // the frequency of each character.
        int[] count = new int[26];
        // Step 2: Create a queue to store the characters in
        // the input stream.
        Queue<char> q = new Queue<char>();
        // Step 3: Initialize an empty string as the answer.
        string answer = "";
 
        foreach(char c in input_stream)
        {
            // Step 4: For each character in the input
            // stream, add it to the queue and increment its
            // frequency in the count array.
            count++;
            q.Enqueue(c);
 
            while (q.Count > 0
                   && count[q.Peek() - 'a'] > 1) {
                // Step 5: While the queue is not empty,
                // check if the frequency of the front
                // character in the queue is 1.
                q.Dequeue();
                // Step 6: If the frequency is greater than
                // 1, remove the front character from the
                // queue.
            }
 
            if (q.Count == 0) {
                // Step 7: If there are no characters left
                // in the queue, append '#' to the answer.
                answer += '#';
            }
            else {
                // Step 6: If the frequency is 1, append the
                // character to the answer.
                answer += q.Peek();
            }
        }
 
        return answer; // Step 8: Return the answer.
    }
 
    public static void Main(string[] args)
    {
        string input_stream
            = "w3wikiandgeeksquizfor";
        string answer = FirstNonRepeatingChar(input_stream);
        Console.WriteLine(answer);
    }
}
// This code is contributed by Prajwal Kandekar

Javascript

// JavaScript code to implement the above approach
function firstNonRepeatingChar(input_stream) {
  // Step 1: Create a count array of size 26 to store the
  // frequency of each character.
  const count = new Array(26).fill(0);
  // Step 2: Create a queue to store the characters in the
  // input stream.
  const q = [];
  // Step 3: Initialize an empty string as the answer.
  let answer = '';
 
  // Step 4: For each character in the input stream, add it to the
  // queue and increment its frequency in the count array.
  for (const c of input_stream) {
    // Increment the frequency of the character in the count array
    count++;
    // Add the character to the queue
    q.push(c);
 
    // Step 5: While the queue is not empty, check if the
    // frequency of the front character in the queue is 1.
    while (q.length > 0 && count[q[0].charCodeAt(0) - 'a'.charCodeAt(0)] > 1) {
      // Step 6: If the frequency is greater than 1, remove the front character
      // from the queue.
      q.shift();
    }
 
    // Step 7: If there are no characters left in the queue, append '#' to the answer.
    // Otherwise, append the front character to the answer.
    answer += q.length > 0 ? q[0] : '#';
  }
 
  // Step 8: Return the answer.
  return answer;
}
 
// Driver code
const input_stream = 'w3wikiandgeeksquizfor';
const answer = firstNonRepeatingChar(input_stream);
console.log(answer);

Output

ggggggggkkksfffffffffffffora

Time complexity: O(n), where n is the number of characters in the stream.
Space complexity: O(n)

Find the first non-repeating character from a stream of characters

Given a stream of characters, find the first non-repeating character from the stream. You need to tell the first non-repeating character in O(1) time at any moment.

If we follow the first approach discussed here, then we need to store the stream so that we can traverse it one more time to find the first non-repeating character at any moment. If we use the extended approach discussed in the same post, we need to go through the count array every time the first non-repeating element is queried. We can find the first non-repeating character from the stream at any moment without traversing any array.

Tags:

#Amazon #array-stream #FactSet #Flipkart #Microsoft #Payu #Yahoo #DSA #Hash #Linked List #Python #Queue #Strings #Amazon #FactSet #Flipkart #Microsoft #Payu #Yahoo #Hash #Linked List #python #Queue #Strings