Queue based approach for first non-repeating character in a stream
Given a stream of characters and we have to find first non repeating character each time a character is inserted to the stream.
Examples:
Input : a a b c Output : a -1 b b Input : a a c Output : a -1 c
We have already discussed a Doubly linked list based approach in the previous post.
Approach:
- Create a count array of size 26(assuming only lower case characters are present) and initialize it with zero.
- Create a queue of char datatype.
- Store each character in queue and increase its frequency in the hash array.
- For every character of stream, we check front of the queue.
- If the frequency of character at the front of queue is one, then that will be the first non-repeating character.
- Else if frequency is more than 1, then we pop that element.
- If queue became empty that means there are no non-repeating characters so we will print -1.
Below is the implementation of above approach:
C++
// C++ program for a Queue based approach // to find first non-repeating character #include <bits/stdc++.h> using namespace std; const int MAX_CHAR = 26; // function to find first non repeating // character of sa stream void firstnonrepeating( char str[]) { queue< char > q; int charCount[MAX_CHAR] = { 0 }; // traverse whole stream for ( int i = 0; str[i]; i++) { // push each character in queue q.push(str[i]); // increment the frequency count charCount[str[i] - 'a' ]++; // check for the non repeating character while (!q.empty()) { if (charCount[q.front() - 'a' ] > 1) q.pop(); else { cout << q.front() << " " ; break ; } } if (q.empty()) cout << -1 << " " ; } cout << endl; } // Driver function int main() { char str[] = "aabc" ; firstnonrepeating(str); return 0; } |
Java
// Java Program for a Queue based approach // to find first non-repeating character import java.util.LinkedList; import java.util.Queue; public class NonReapatingCQueue { final static int MAX_CHAR = 26 ; // function to find first non repeating // character of stream static void firstNonRepeating(String str) { // count array of size 26(assuming // only lower case characters are present) int [] charCount = new int [MAX_CHAR]; // Queue to store Characters Queue<Character> q = new LinkedList<Character>(); // traverse whole stream for ( int i = 0 ; i < str.length(); i++) { char ch = str.charAt(i); // push each character in queue q.add(ch); // increment the frequency count charCount[ch - 'a' ]++; // check for the non repeating character while (!q.isEmpty()) { if (charCount[q.peek() - 'a' ] > 1 ) q.remove(); else { System.out.print(q.peek() + " " ); break ; } } if (q.isEmpty()) System.out.print(- 1 + " " ); } System.out.println(); } // Driver function public static void main(String[] args) { String str = "aabc" ; firstNonRepeating(str); } } // This code is Contributed by Sumit Ghosh |
Python3
# Python3 program for a Queue based approach # to find first non-repeating character from queue import Queue # function to find first non # repeating character of sa Stream def firstnonrepeating( Str ): global MAX_CHAR q = Queue() charCount = [ 0 ] * MAX_CHAR # traverse whole Stream for i in range ( len ( Str )): # push each character in queue q.put( Str [i]) # increment the frequency count charCount[ ord ( Str [i]) - ord ( 'a' )] + = 1 # check for the non repeating # character while ( not q.empty()): if (charCount[ ord (q.queue[ 0 ]) - ord ( 'a' )] > 1 ): q.get() else : print (q.queue[ 0 ], end = " " ) break if (q.empty()): print ( - 1 , end = " " ) print () # Driver Code MAX_CHAR = 26 Str = "aabc" firstnonrepeating( Str ) # This code is contributed by PranchalK |
C#
using System; using System.Collections.Generic; // C# Program for a Queue based approach // to find first non-repeating character public class NonReapatingCQueue { public const int MAX_CHAR = 26; // function to find first non repeating // character of stream public static void firstNonRepeating( string str) { // count array of size 26(assuming // only lower case characters are present) int [] charCount = new int [MAX_CHAR]; // Queue to store Characters LinkedList< char > q = new LinkedList< char >(); // traverse whole stream for ( int i = 0; i < str.Length; i++) { char ch = str[i]; // push each character in queue q.AddLast(ch); // increment the frequency count charCount[ch - 'a' ]++; // check for the non repeating character while (q.Count > 0) { if (charCount[q.First.Value - 'a' ] > 1) { q.RemoveFirst(); } else { Console.Write(q.First.Value + " " ); break ; } } if (q.Count == 0) { Console.Write(-1 + " " ); } } Console.WriteLine(); } // Driver function public static void Main( string [] args) { string str = "aabc" ; firstNonRepeating(str); } } //This code is contributed by Shrikant13 |
Javascript
<script> // JavaScript Program for a Queue based approach // to find first non-repeating character const MAX_CHAR = 26; // function to find first non repeating // character of stream function firstNonRepeating(str) { // count array of size 26(assuming // only lower case characters are present) var charCount = new Array(MAX_CHAR).fill(0); // Queue to store Characters var q = []; // traverse whole stream for ( var i = 0; i < str.length; i++) { var ch = str[i]; // push each character in queue q.push(ch); // increment the frequency count charCount[ch.charCodeAt(0) - "a" .charCodeAt(0)]++; // check for the non repeating character while (q.length > 0) { if (charCount[q[0].charCodeAt(0) - "a" .charCodeAt(0)] > 1) { q.shift(); } else { document.write(q[0] + " " ); break ; } } if (q.length == 0) { document.write(-1 + " " ); } } document.write( "<br>" ); } // Driver function var str = "aabc" ; firstNonRepeating(str); </script> |
Output:
a -1 b b
Time complexity : O(n)
Auxiliary Space : O(n)
Contact Us