First non-repeating character in a stream

Hari Sapna Nair
Last Updated: May 13, 2022

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 (DSA) 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, Adobe, etc. 

 

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.

First non-repeating character in a stream: 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.

 

For 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.

 

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 find the first non-repeating character in a stream.

First non-repeating character in a stream: Using Queue

In this approach, a queue 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.
     

 

Working

 

Code:

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.

First non-repeating character in a stream: 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.

 

Working

 

Code:

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.

 

Frequently Asked Questions

  1. What is the time complexity to insert the node at the end and delete the node in a doubly-linked list?
    Ans:- O(1) will be the time complexity as there is no need for any traversal in this case.
     
  2. Why is the doubly-linked list used instead of an array?
    Ans:- Deletion operations cannot be performed easily in the case of arrays.
     
  3. Why is the use of queues preferred in this problem?
    Ans:- Queues are preferred for the dynamic addition and deletion of nodes. The tasks like adding a node, removing a node, accessing node, etc.,  are efficiently performed with  O(1) time complexity.
     

Key Takeaways

This blog covered the various methods to find the first non-repeating character in a stream. The methods discussed are using the queues and the doubly linked lists.

Don't stop here. Check out our Data Structures and Algorithms-guided path to learn Data Structures and Algorithms from scratch. We hope you found this blog useful. Feel free to comment down below if you have a better insight into the above approach.

Was this article helpful ?
1 upvote

Comments

No comments yet

Be the first to share what you think