Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Problem Statement
2.1.
Example
2.2.
Explanation:
3.
Approach 1: Using Queue
3.1.
Steps
3.2.
Code
3.3.
Java
3.4.
Complexity Analysis
4.
Approach 2: Using Doubly Linked List
4.1.
Steps 
4.2.
Code
4.3.
Java
4.4.
Complexity Analysis
5.
Approach 3: Using Hashing
5.1.
Steps
5.2.
Code
5.3.
Java
5.4.
Complexity Analysis
6.
Approach 4: Using a Count Array
6.1.
Steps
6.2.
Code
6.3.
Java
6.4.
Complexity Analysis
7.
Frequently Asked Questions
7.1.
What function finds the first non repeating character?
7.2.
What is the first non-repeating character in a stream stack?
7.3.
How to find first non repeated character in a string using stream?
7.4.
What is the program to find the first non repeated character in a word?
8.
Conclusion
8.1.
Recommended Problems
Last Updated: Mar 27, 2024
Medium

Find the First Non-Repeating Character in a Stream

Author Hari Sapna Nair
7 upvotes

Introduction 

A good programmer is the one who can write the most optimized codes. To develop this ability, the knowledge of data structures and algorithms becomes essential. Due to this reason, the knowledge of Data Structures and Algorithms is frequently tested in interviews for SDE(Software Development Engineering) roles. The importance of DSA cannot be emphasized enough, especially if you aim to get placed in product-based companies like Google, Amazon, Microsoft, etc. 

First Non Repeating Character in a Stream

For questions related to each data structure, refer to the blog Must-Do Coding Interview Questions for Product Based Companies.

This blog will discuss the interview problem: find the first non-repeating character in a stream previously asked in companies like Amazon, Adobe, Microsoft, Yahoo, etc.

Problem Statement

Given an input stream of characters consisting only of lowercase alphabets.  Find the first non-repeating character in the input string each time a new character is inserted into the stream. If there is no non-repeating character, then append '-1' to the answer.

Example

Input:

aabcbc
Output:

a -1 b b c -1 

Explanation:

  • When the input stream is "a,"  the first non-repeating character, "a," is appended.
  • When the input stream is "aa,"  there is no first non-repeating character, so "-1" is appended.
  • When the input stream is "aab,"  the first non-repeating character, "b," is appended.
  • When the input stream is "aabc,"  the first non-repeating character, "b," is appended.
  • When the input stream is "aabcb,"  the first non-repeating character, "c," is appended.
  • When the input stream is "aabcbc," there is no first non-repeating character, so "-1" is appended.

 

first non-repeating character

Explanation

 

Recommended: Please try to solve the “First Unique Character in the String” on "CODESTUDIO" first before moving on to the solution. 

Now let's see various approaches to finding the first non-repeating character in a stream.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 1: Using Queue

In this approach, a queue data structure and a character array are used. The frequency of the characters is stored in the frequencyCount array, and the characters are stored in the queue. If the frequencyCount is greater than 1, the character is removed from the queue as it is repeating. Else, the front element of the queue is displayed. If the queue is empty, i.e., no more non-repeating characters are present, -1 is printed.

Steps

  1. Create a character array to store the frequency count of the characters.
  2. Create a queue to store the characters.
  3. Traverse the string.
  4. And the character and increment the frequency count.
  5. If the queue contains repeating characters, remove the character from the queue.
  6. If the queue contains repeating non-repeating characters, display the front element of the queue and break the while loop.
  7. If the queue is empty, i.e., no more non-repeating characters are present, -1 is printed.
queue data structure

 

Working

 

Code

  • Java

Java

import java.util.LinkedList;
import java.util.Queue;

public class Main {

public static String firstNonRepeatingCharacter(String str) {
   StringBuilder resultantString = new StringBuilder();
   int[] characterFrequency = new int[26];

   // queue to store the characters
   Queue<Character> queue = new LinkedList<Character>();

   // traverse whole stream of characters
   for (int i = 0; i < str.length(); i++) {
     char ch = str.charAt(i);

     // push the character into the queue
     queue.add(ch);

     // increment the frequency count
     characterFrequency[ch - 'a']++;

     // check for the non repeating character
     while (!queue.isEmpty()) {
       // when the character is repeated
       if (characterFrequency[queue.peek() - 'a'] > 1)
         queue.remove();
       // when the character is not repeating
       else {
         resultantString.append(queue.peek() + " ");
         break;
       }
     }

     // if there is no non-repeating character
     if (queue.isEmpty())
       resultantString.append("-1 ");
   }
  
   return resultantString.toString();
}

public static void main(String[] args) {
   String str = "aabcbc";
   String result = firstNonRepeatingCharacter(str);
   System.out.println(result);
}
}

Output

a -1 b b c -1

Complexity Analysis

Time Complexity: O(n) as the string is traversed once.

Space Complexity: O(n)  as extra space is required to store the characters in the queue.

Where "n" is the number of characters in the string.

Approach 2: Using Doubly Linked List

In this approach, a Doubly Linked List and a hashmap are used. The Doubly Linked List stores the characters, and the hashmap stores the character as the key and the node( storing the character) as the value. If the hashmap does not contain the character, the character is stored in the hashmap and doubly linked list. Else, the value of the character is set to null in the hashmap. 

Steps 

  • Create a hashmap to store the character and node.
  • Create a doubly linked list to store the characters.
  • Traverse the string.
  • If the hashmap does not contain the character:
    • Add character to the doubly linked list.
    • Add the node containing character to the hashmap with character as the key.
    • Add the character stored in the head of the doubly linked list to the resultant string.
  • If the hashmap contains the character:
    • If the character is repeating and the node is not null, delete the node and store the value as null in the hashmap.
    • If the head is null, add -1 to the resultant string. Else add the character value of the head node.
doubly linked list

Working

 

Code

  • Java

Java

import java.util.HashMap;

// node of the doubly linked list
class Node {
char ch;
 Node previous;
 Node next;

 Node(char ch) {
   this.ch = ch;
}
}

public class Main {
// head and tail of the doubly linked list
 Node head = null, tail = null;

// add node at the end of the doubly linked list
public void addNode(char ch) {
   Node newNode = new Node(ch);
  
   // if doubly linked list is empty
   if (head == null) {
     head = tail = newNode;
     return;
   }
  
   // if doubly linked list is not empty
   tail.next = newNode;
   newNode.previous = tail;
   tail = newNode;
}

// delete the node of the doubly linked list
void deleteNode(Node del) {
   // if doubly linked list is empty or the node to be deleted is empty
   if (head == null || del == null) {
     return;
   }

   // delete head node
   if (head == del) {
     head = del.next;
   }

   // delete tail node
   if (tail == del)
     tail = tail.previous;

   // change next pointer only if node to be deleted is not the tail node
   if (del.next != null) {
     del.next.previous = del.previous;
   }

   // change previous pointer only if node to be deleted is not the first node
   if (del.previous != null) {
     del.previous.next = del.next;
   }
  
   return;
}

// function that returns the string of first non repeating characters
public static String firstNonRepeatingCharacter(String str) {
   StringBuilder resultantString = new StringBuilder();
   // hashmap to store the character and node
   HashMap<Character, Node> hashmap = new HashMap<Character, Node>();
  
   // doubly linked list
   Main dll = new Main();

   for (int i = 0; i < str.length(); i++) {
     char ch = str.charAt(i);
     // if the hashmap does not contain the character
     if (!hashmap.containsKey(ch)) {
       // add the node to the doubly linked list
       dll.addNode(ch);
       // add the character to hashmap
       hashmap.put(ch, dll.tail);
       // add the character to the resultant string
       resultantString.append(dll.head.ch + " ");
     } else {
       // if the character is encountered for the second time
       if (hashmap.get(ch) != null) {
         dll.deleteNode(hashmap.get(ch));
       // replace the node of the respective character with null
         hashmap.replace(ch, null);
       }
       if (dll.head == null) {
         resultantString.append("-1 ");
       } else {
         resultantString.append(dll.head.ch + " ");
       }
     }
   }

   return resultantString.toString();
}

// driver Code
public static void main(String[] args) {
   String str = "aabcbc";
   String result = firstNonRepeatingCharacter(str);
   System.out.println(result);
}
}

Output:

a -1 b b c -1

Complexity Analysis

Time Complexity: O(n) as the string is traversed once.

Space Complexity: O(n)  as extra space is required to store the doubly linked list and the hashmap.

Where "n" is the number of characters in the string.

Approach 3: Using Hashing

To find the first non-repeating character in a stream using hashing, we can maintain a data structure to store the frequency of each character as it appears in the stream. Additionally, we need to keep track of the order of appearance of characters. A LinkedHashMap, which maintains insertion order, is suitable for this task.

Steps

  • Initialize a LinkedHashMap to store the frequency of characters and their order of appearance.
  • For each character in the stream:
    • If the character is not present in the LinkedHashMap, add it with a frequency of 1.
    • If the character is already present, increment its frequency.
  • Iterate through the LinkedHashMap to find the first character with a frequency of 1. This represents the first non-repeating character.

Code

  • Java

Java

import java.util.LinkedHashMap;
import java.util.Map;

class FirstNonRepeatingCharacter {
public static char findFirstNonRepeatingCharacter(String stream) {
Map<Character, Integer> frequencyMap = new LinkedHashMap<>();

for (char ch : stream.toCharArray()) {
frequencyMap.put(ch, frequencyMap.getOrDefault(ch, 0) + 1);
}

for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
if (entry.getValue() == 1) {
return entry.getKey();
}
}

// If no non-repeating character is found, return a placeholder
return '\0';
}

public static void main(String[] args) {
String stream = "aabbcdde";
char result = findFirstNonRepeatingCharacter(stream);

System.out.println("First Non-Repeating Character: " + result);
}
}

Output:

First Non-Repeating Character: c

Complexity Analysis

Time Complexity: O(N) where N is the length of the input stream. We iterate through the stream once.

Space Complexity: O(K) where K is the number of unique characters in the stream. 

Approach 4: Using a Count Array

To find the first non-repeating character in a stream using a count array, we can maintain an array to store the count of each character's occurrence in the stream. Additionally, we need to keep track of the order of appearance of characters. A separate array or data structure can be used to store the order of appearance.

Steps

  • Initialize an array to store the count of each character's occurrence (e.g., countArray) and an array to store the order of appearance (e.g., orderArray).
  • Initialize an index to keep track of the order.
  • For each character in the stream:
    • Update the count of the character in countArray.
    • If the count becomes 1, update the orderArray at the current index with the character and increment the index.
  • Iterate through the orderArray to find the first character with a count of 1. This represents the first non-repeating character.

Code

  • Java

Java

class FirstNonRepeatingCharacter {
// Assuming ASCII characters
static final int CHAR_RANGE = 256;

public static char findFirstNonRepeatingCharacter(String stream) {
int[] countArray = new int[CHAR_RANGE];
char[] orderArray = new char[stream.length()];
int index = 0;

for (char ch : stream.toCharArray()) {
countArray[ch]++;
if (countArray[ch] == 1) {
orderArray[index++] = ch;
}
}

for (int i = 0; i < index; i++) {
if (countArray[orderArray[i]] == 1) {
return orderArray[i];
}
}

// If no non-repeating character is found, return a placeholder
return '\0';
}

public static void main(String[] args) {
String stream = "aabccdde";
char result = findFirstNonRepeatingCharacter(stream);

System.out.println("First Non-Repeating Character: " + result);
}
}

Output:

First Non-Repeating Character: b

Complexity Analysis

Time Complexity: O(N) where N is the length of the input stream. We iterate through the stream once.

Space Complexity: O(K) where K is the number of unique characters in the stream.

Frequently Asked Questions

What function finds the first non repeating character?

We can create a function in Java that uses a LinkedHashMap to maintain character counts in the order of appearance. It iterates through the input string, then through the map to find and return the first non-repeating character or a placeholder ('\0').

What is the first non-repeating character in a stream stack?

If the character given is aabccdd. Here the occurrence of a is 2, b is 1, c is 2, and d is 2. The character which is not repeated in the first time is b. So, the first non-repeating character is b.  

How to find first non repeated character in a string using stream?

Scan the string, then save the number of characters in a hashmap. Get a character count for each character in String by traversing the Map. When we are reading a string from start to last, if any character's count is 1, return that character.

What is the program to find the first non repeated character in a word?

In Java, we may locate the first non-repeating character in a string using the indexOf() and lastIndexOf() methods.

public class Main {
   public static void main(String args[]) {
    
       String str ="abbbcccda";
       for(char i :str.toCharArray()){
       if ( str.indexOf(i) == str.lastIndexOf(i)) {
           System.out.println("First non-repeating character is: "+i);
           break;
       }
       }
   }
}

Conclusion

This blog discussed the various methods to find the first non-repeating character in a stream along with their implementation using data structures such as queue, array, hashmaps, and doubly-linked lists.

Recommended Problems

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests and some more Interview Experiences curated by top Industry Experts only on  Coding Ninjas Studio.

Cheers!

Previous article
Generate a Permutation of First N Natural Numbers having Count of Unique Adjacent Differences Equal to K
Next article
How to Efficiently Implement K Queues in a Single Array?
Live masterclass