Find the first non-repeating character from a stream of characters
Last Updated :
23 Nov, 2023
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.
Find the first non-repeating character from a stream of characters using Hashing:
The idea is to maintain a hashmap that uses constant space of at max 26 entries. This will keep the track of characters already encountered in the string and do so in constant query time. Secondly, an ArrayList or Vector can be used to keep track of the current unique characters from the beginning which should be added to the resultant string. Whenever any unique character is encountered again, it’s removed from the vector, but kept in HashMap to mark it as encountered. If the list is empty at any point, this means there is no non-repeating character present in the string, hence ‘#’ can be added.
Below is the implementation of the above code:
C++
#include <bits/stdc++.h>
using namespace std;
string FirstNonRepeating(string A)
{
vector<char> v;
unordered_map<char, int> mp;
string ans;
for (char ch : A) {
if (mp.find(ch)
== mp.end()) {
v.push_back(ch);
mp[ch] = 1;
}
else {
int index
= find(v.begin(), v.end(), ch) - v.begin();
if (index < v.size())
v.erase(v.begin() + index);
}
ans += (v.empty() ? '#' : v.front());
}
return ans;
}
int main()
{
string A = "geeksforgeeksandgeeksquizfor";
string ans = FirstNonRepeating(A);
cout << ans << endl;
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
static String FirstNonRepeating(String A)
{
ArrayList<Character> list = new ArrayList<>();
HashMap<Character, Integer> map = new HashMap<>();
StringBuilder sb = new StringBuilder();
for (char ch : A.toCharArray()) {
if (!map.containsKey(ch)) {
list.add(ch);
map.put(ch, 1);
}
else {
int index = list.indexOf(ch);
if (index != -1)
list.remove(index);
}
sb.append(list.isEmpty() ? '#' : list.get(0));
}
return sb.toString();
}
public static void main(String[] args)
{
String A = "geeksforgeeksandgeeksquizfor";
String ans = FirstNonRepeating(A);
System.out.print(ans);
}
}
|
Python3
def FirstNonRepeating(A):
list = []
mp = {}
ans = ''
for ch in A:
if ch not in mp:
list.append(ch)
mp[ch] = 1
else:
if ch in list:
list.remove(ch)
ans += list[0] if list else '#'
return ans
l = "geeksforgeeksandgeeksquizfor"
ans1 = FirstNonRepeating(l)
print(ans1)
|
C#
using System;
using System.Collections.Generic;
public class GFG {
static string FirstNonRepeating(string A)
{
List<char> list = new List<char>();
Dictionary<char, int> map
= new Dictionary<char, int>();
string result = "";
foreach(char ch in A)
{
if (!map.ContainsKey(
ch))
{
list.Add(ch);
map.Add(ch, 1);
}
else {
int index = list.IndexOf(ch);
if (index != -1) {
list.RemoveAt(index);
}
}
result += (list.Count == 0 ? '#' : list[0]);
}
return result;
}
static void Main(string[] args)
{
string A = "geeksforgeeksandgeeksquizfor";
string ans = FirstNonRepeating(A);
Console.WriteLine(ans);
}
}
|
Javascript
<script>
function firstNonRepeating(A) {
let list = [];
let map = new Map();
let sb = "";
for (let i = 0; i < A.length; i++) {
let ch = A.charAt(i);
if (!map.has(ch)) {
list.push(ch);
map.set(ch, 1);
} else {
let index = list.indexOf(ch);
if (index != -1) {
list.splice(index, 1);
}
}
sb += (list.length === 0 ? '#' : list[0]);
}
return sb;
}
let A = "geeksforgeeksandgeeksquizfor";
let ans = firstNonRepeating(A);
document.write(ans);
</script>
|
Output
ggggggggkkksfffffffffffffora
Time Complexity: O(26 * n)
Auxiliary Space: O(n)
Find the first non-repeating character from a stream of characters using Double Ended Linklist:
The idea is to use a DLL (Doubly Linked List) to efficiently get the first non-repeating character from a stream. The DLL contains all non-repeating characters in order, i.e., the head of DLL contains first non-repeating character, the second node contains the second non-repeating, and so on.
We also maintain two arrays: one array is to maintain characters that are already visited two or more times, we call it repeated[], the other array is an array of pointers to linked list nodes, we call it inDLL[]. The size of both arrays is equal to alphabet size which is typically 256.
Step-by-step approach:
- Create an empty DLL. Also, create two arrays inDLL[] and repeated[] of size 256. In DLL is an array of pointers to DLL nodes. repeated[] is a boolean array, repeated[x] is true if x is repeated two or more times, otherwise false. inDLL[x] contains a pointer to a DLL node if character x is present in DLL, otherwise NULL.
- Initialize all entries of inDLL[] as NULL and repeated[] as false.
- To get the first non-repeating character, return character at the head of DLL.
- Following are steps to process a new character ‘x’ in a stream.
- If repeated[x] is true, ignore this character (x is already repeated two or more times in the stream)
- If repeated[x] is false and inDLL[x] is NULL (x is seen the first time). Append x to DLL and store address of new DLL node in inDLL[x].
- If repeated[x] is false and inDLL[x] is not NULL (x is seen a second time). Get DLL node of x using inDLL[x] and remove the node. Also, mark inDLL[x] as NULL and repeated[x] as true.
Note that appending a new node to DLL is O(1) operation if we maintain a tail pointer. Removing a node from DLL is also O(1). So both operations, addition of new character and finding first non-repeating character take O(1) time.
Illustration:
Below is the implementation of the above approach:
C++
#include <iostream>
#define MAX_CHAR 256
using namespace std;
struct node {
char a;
struct node *next, *prev;
};
void appendNode(struct node** head_ref,
struct node** tail_ref, char x)
{
struct node* temp = new node;
temp->a = x;
temp->prev = temp->next = NULL;
if (*head_ref == NULL) {
*head_ref = *tail_ref = temp;
return;
}
(*tail_ref)->next = temp;
temp->prev = *tail_ref;
*tail_ref = temp;
}
void removeNode(struct node** head_ref,
struct node** tail_ref, struct node* temp)
{
if (*head_ref == NULL)
return;
if (*head_ref == temp)
*head_ref = (*head_ref)->next;
if (*tail_ref == temp)
*tail_ref = (*tail_ref)->prev;
if (temp->next != NULL)
temp->next->prev = temp->prev;
if (temp->prev != NULL)
temp->prev->next = temp->next;
delete (temp);
}
void findFirstNonRepeating()
{
struct node* inDLL[MAX_CHAR];
bool repeated[MAX_CHAR];
struct node *head = NULL, *tail = NULL;
for (int i = 0; i < MAX_CHAR; i++) {
inDLL[i] = NULL;
repeated[i] = false;
}
char stream[] = "geeksforgeeksandgeeksquizfor";
for (int i = 0; stream[i]; i++) {
char x = stream[i];
cout << "Reading " << x << " from stream \n";
if (!repeated[x]) {
if (inDLL[x] == NULL) {
appendNode(&head, &tail, stream[i]);
inDLL[x] = tail;
}
else
{
removeNode(&head, &tail, inDLL[x]);
inDLL[x] = NULL;
repeated[x]
= true;
}
}
if (head != NULL)
cout << "First non-repeating character so far "
"is "
<< head->a << endl;
}
}
int main()
{
findFirstNonRepeating();
return 0;
}
|
Java
import java.util.ArrayList;
import java.util.List;
public class NonReapeatingC {
final static int MAX_CHAR = 256;
static void findFirstNonRepeating()
{
List<Character> inDLL = new ArrayList<Character>();
boolean[] repeated = new boolean[MAX_CHAR];
String stream = "geeksforgeeksandgeeksquizfor";
for (int i = 0; i < stream.length(); i++) {
char x = stream.charAt(i);
System.out.println("Reading " + x
+ " from stream \n");
if (!repeated[x]) {
if (!(inDLL.contains(x))) {
inDLL.add(x);
}
else
{
inDLL.remove((Character)x);
repeated[x]
= true;
}
}
if (inDLL.size() != 0) {
System.out.print(
"First non-repeating character so far is ");
System.out.println(inDLL.get(0));
}
}
}
public static void main(String[] args)
{
findFirstNonRepeating();
}
}
|
Python3
MAX_CHAR = 256
def findFirstNonRepeating():
inDLL = [] * MAX_CHAR
repeated = [False] * MAX_CHAR
stream = "geekforgeekandgeeksandquizfor"
for i in range(len(stream)):
x = stream[i]
print ("Reading " + x + " from stream")
if not repeated[ord(x)]:
if not x in inDLL:
inDLL.append(x)
else:
inDLL.remove(x)
repeated[ord(x)] = True
if len(inDLL) != 0:
print ("First non-repeating character so far is ")
print (str(inDLL[0]))
findFirstNonRepeating()
|
C#
using System;
using System.Collections.Generic;
public class NonReapeatingC {
readonly static int MAX_CHAR = 256;
static void findFirstNonRepeating()
{
List<char> inDLL = new List<char>();
bool[] repeated = new bool[MAX_CHAR];
String stream = "geeksforgeeksandgeeksquizfor";
for (int i = 0; i < stream.Length; i++) {
char x = stream[i];
Console.WriteLine("Reading " + x + " from stream \n");
if (!repeated[x]) {
if (!(inDLL.Contains(x))) {
inDLL.Add(x);
}
else
{
inDLL.Remove((char)x);
repeated[x] = true;
}
}
if (inDLL.Count != 0) {
Console.Write("First non-repeating character so far is ");
Console.WriteLine(inDLL[0]);
}
}
}
public static void Main(String[] args)
{
findFirstNonRepeating();
}
}
|
Javascript
<script>
let MAX_CHAR = 256;
function findFirstNonRepeating()
{
let inDLL = [];
let repeated = new Array(MAX_CHAR);
for(let i = 0; i < MAX_CHAR; i++)
{
repeated[i] = false;
}
let stream = "geeksforgeeksandgeeksquizfor";
for(let i = 0; i < stream.length; i++)
{
let x = stream[i];
document.write("Reading " + x +
" from stream <br>");
if (!repeated[x.charCodeAt(0)])
{
if (!(inDLL.includes(x)))
{
inDLL.push(x);
}
else
{
inDLL.splice(inDLL.indexOf(x), 1);
repeated[x.charCodeAt(0)] = true;
}
}
if (inDLL.length != 0)
{
document.write("First non-repeating " +
"character so far is ");
document.write(inDLL[0] + "<br>");
}
}
}
findFirstNonRepeating();
</script>
|
Output
Reading g from stream
First non-repeating character so far is g
Reading e from stream
First non-repeating character so far is g
Reading e from stream
First non-repeating character so far is g
Readi...
Time Complexity: O(n)
Auxiliary Space: O(1)
Note: The Python code has complexity of O(n^2) because in operator is being used inside the loop which has complexity of O(n).
Find the first non-repeating character from a stream of characters using Queue:
This problem can be solved using queue, push into the queue every time when unique character is found and pop it out when you get front character of queue repeated in the stream , this is how first non-repeated character in managed.
Follow the below steps to solve the given problem:
- Take map to check the uniqueness of an element.
- Take queue to find first non-repeating element.
- Traverse through the string and increase the count of elements in map and push in to queue is count is 1.
- If count of front element of the queue > 1 anytime then pop it from the queue until we get unique element at the front.
- If queue is empty anytime append answer string with ‘#’ else append it with front element of queue.
- return answer string.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
string FirstNonRepeating(string A)
{
string ans = "";
unordered_map<char, int> mp;
queue<char> q;
for (int i = 0; i < A.length(); i++) {
if (mp.find(A[i]) == mp.end()) {
q.push(A[i]);
}
mp[A[i]]++;
while (!q.empty() && mp[q.front()] > 1) {
q.pop();
}
if (!q.empty()) {
ans += q.front();
}
else {
ans += '#';
}
}
return ans;
}
int main()
{
string A = "geeksforgeeksandgeeksquizfor";
string ans = FirstNonRepeating(A);
cout << ans << "\n";
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
static String FirstNonRepeating(String A)
{
String ans = "";
Map<Character, Integer> mp = new HashMap<>();
Queue<Character> q = new LinkedList<>();
for (int i = 0; i < A.length(); i++)
{
if (!mp.containsKey(A.charAt(i))) {
q.add(A.charAt(i));
}
mp.put(A.charAt(i),
mp.getOrDefault(A.charAt(i), 0) + 1);
while (!q.isEmpty() && (mp.get(q.peek()) > 1)) {
q.remove();
}
if (!q.isEmpty()) {
ans += q.peek();
}
else {
ans += '#';
}
}
return ans;
}
public static void main(String[] args)
{
String A = "geeksforgeeksandgeeksquizfor";
String ans = FirstNonRepeating(A);
System.out.print(ans);
}
}
|
Python
from collections import deque
def FirstNonRepeating(A):
ans = ""
mp = {}
q = deque()
for i in range(len(A)):
if A[i] not in mp:
q.append(A[i])
mp[A[i]] = mp.get(A[i], 0) + 1
while len(q) > 0 and mp[q[0]] > 1:
q.popleft()
if len(q) > 0:
ans += q[0]
else:
ans += "#"
return ans
A = "geeksforgeeksandgeeksquizfor"
ans = FirstNonRepeating(A)
print(ans)
|
C#
using System;
using System.Collections.Generic;
public class GFG {
public static string FirstNonRepeating(string A)
{
string ans = "";
Dictionary<char, int> mp
= new Dictionary<char, int>();
Queue<char> q = new Queue<char>();
for (int i = 0; i < A.Length; i++)
{
if (!mp.ContainsKey(A[i])) {
q.Enqueue(A[i]);
}
if (mp.ContainsKey(A[i]))
mp[A[i]] += 1;
else
mp[A[i]] = 1;
while (q.Count > 0 && mp[q.Peek()] > 1) {
q.Dequeue();
}
if (q.Count > 0) {
ans += q.Peek();
}
else {
ans += '#';
}
}
return ans;
}
static public void Main()
{
string A = "geeksforgeeksandgeeksquizfor";
string ans = FirstNonRepeating(A);
Console.WriteLine(ans);
}
}
|
Javascript
function FirstNonRepeating(A)
{
let ans = "";
let mp = new Map();
for(let i=97;i<123;i++)
{
mp.set(String.fromCharCode(i),0);
}
let q = [];
for (let i = 0; i < A.length; i++)
{
if (mp.get(A[i])==0) {
q.push(A[i]);
}
mp.set(A[i],mp.get(A[i])+1);
while (q.length>0 && mp.get(q[0])> 1) {
q.shift();
}
if (q.length>0) {
ans += q[0];
}
else {
ans += '#';
}
}
return ans;
}
let A = "geeksforgeeksandgeeksquizfor";
let ans = FirstNonRepeating(A);
console.log(ans);
|
Output
ggggggggkkksfffffffffffffora
Time Complexity: O(26 * n)
Auxiliary Space: O(n)
Find the first non-repeating character from a stream of characters using a Count Array:
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++
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
string firstNonRepeatingChar(string input_stream)
{
int count[26] = { 0 };
queue<char> q;
string answer = "";
for (char c :
input_stream) {
count++;
q.push(c);
while (!q.empty()
&& count[q.front() - 'a']
> 1) {
q.pop();
}
if (q.empty()) {
answer += '#';
}
else {
answer += q.front();
}
}
return answer;
}
int main()
{
string input_stream = "geeksforgeeksandgeeksquizfor";
string answer = firstNonRepeatingChar(input_stream);
cout << answer << endl;
return 0;
}
|
Java
import java.util.*;
public class Main {
public static String
firstNonRepeatingChar(String input_stream)
{
int[] count = new int[26];
Queue<Character> q = new LinkedList<>();
String answer = "";
for (char c : input_stream.toCharArray()) {
count++;
q.add(c);
while (!q.isEmpty()
&& count[q.peek() - 'a'] > 1) {
q.remove();
}
if (q.isEmpty()) {
answer += '#';
}
else {
answer += q.peek();
}
}
return answer;
}
public static void main(String[] args)
{
String input_stream
= "geeksforgeeksandgeeksquizfor";
String answer = firstNonRepeatingChar(input_stream);
System.out.println(answer);
}
}
|
Python
from collections import deque
def first_non_repeating_char(input_stream):
count = [0] * 26
q = deque()
answer = ""
for c in input_stream:
count[ord(c) - ord('a')] += 1
q.append(c)
while q and count[ord(q[0]) - ord('a')] > 1:
q.popleft()
if not q:
answer += '#'
else:
answer += q[0]
return answer
input_stream = "geeksforgeeksandgeeksquizfor"
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)
{
int[] count = new int[26];
Queue<char> q = new Queue<char>();
string answer = "";
foreach(char c in input_stream)
{
count++;
q.Enqueue(c);
while (q.Count > 0
&& count[q.Peek() - 'a'] > 1) {
q.Dequeue();
}
if (q.Count == 0) {
answer += '#';
}
else {
answer += q.Peek();
}
}
return answer;
}
public static void Main(string[] args)
{
string input_stream
= "geeksforgeeksandgeeksquizfor";
string answer = FirstNonRepeatingChar(input_stream);
Console.WriteLine(answer);
}
}
|
Javascript
function firstNonRepeatingChar(input_stream) {
const count = new Array(26).fill(0);
const q = [];
let answer = '';
for (const c of input_stream) {
count++;
q.push(c);
while (q.length > 0 && count[q[0].charCodeAt(0) - 'a'.charCodeAt(0)] > 1) {
q.shift();
}
answer += q.length > 0 ? q[0] : '#';
}
return answer;
}
const input_stream = 'geeksforgeeksandgeeksquizfor';
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)
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...