CC-17 : Find and return index of first non-repeating char at all indexes before current.

Description:

Given a stream of characters, find index of first non-repeating char at all indexes before current index.

Test cases and expected outputs:

Input Parameters	Expected outputs
String stream="aabbccdee"; System.out.println("Input String: "+stream); QueueFirstNonRepeating queueFirstNonRepeating = new QueueFirstNonRepeating(); StringFirstNonRepeatingAtIdx= queueFirstNonRepeating.queueFirstNonRepeating(stream); System.out.println("Nonrep at idx: "+firstNonRepeatingAtIdx);	Input String: aabbccdee Non rep at idx: a#b#c#ddd

Pseudocode:

Declare and initialize a HashMap to hold frequencies of occurrence of data elements in the input stream of characters.

Declare and initialize a Queue to unique characters found in the input stream of characters.

Declare a String firstNonRepeatingAtIdx to hold first non repeating character at each index.

If the current character does not exist in the HashMap, add it to HashMap with frequency of 1, else increment its current frequency by 1.

If frequency of current character is 1, it means it is unique number found so far, so add it to Queue holding unique numbers.

While Queue holding unique characters is not empty and the current element from Queue holding unique characters is non unique (check this using HashMap holding frequencies of characters), remove the character from the queue.

When above while loop completes and Queue size is non zero then the first character in the queue is the first unique character in the stream within in all processed characters. Append this character to the String firstNonRepeatingAtIdx.

If the Queue size is 0 after above while loop, that means there is no current first unique number in the Queue. To indicate this, append this “#” to the String firstNonRepeatingAtIdx.

Code:

public String queueFirstNonRepeating(String stream) {
	HashMap<Character, Integer> cnts=new  HashMap<Character,Integer>();
	Queue<Character> uniQueue=new LinkedList<Character>();
	String firstNonRepeatingAtIdx=new String();
	char chr;
	for (int idx=0;idx < stream.length(); idx++) {
		chr=stream.charAt(idx);
		cnts.put(chr, cnts.getOrDefault(chr,0)+1);
		if (cnts.getOrDefault(chr,0)==1) {
			uniQueue.add(chr);
		}
		while ((uniQueue.size() !=0) && ( cnts.getOrDefault(uniQueue.element(),0) > 1)) {
			uniQueue.remove();
		}
		if (uniQueue.size() !=0) {
			firstNonRepeatingAtIdx+=uniQueue.element();
		}else {
			firstNonRepeatingAtIdx+="#";
		}		
	}
	return firstNonRepeatingAtIdx;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

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


public class QueueFirstNonRepeating {
	
public String queueFirstNonRepeating(String stream) {
	HashMap<Character, Integer> cnts=new  HashMap<Character,Integer>();
	Queue<Character> uniQueue=new LinkedList<Character>();
	String firstNonRepeatingAtIdx=new String();
	char chr;
	for (int idx=0;idx < stream.length(); idx++) {
		chr=stream.charAt(idx);
		cnts.put(chr, cnts.getOrDefault(chr,0)+1);
		if (cnts.getOrDefault(chr,0)==1) {
			uniQueue.add(chr);
		}
		while ((uniQueue.size() !=0) && ( cnts.getOrDefault(uniQueue.element(),0) > 1)) {
			uniQueue.remove();
		}
		if (uniQueue.size() !=0) {
			firstNonRepeatingAtIdx+=uniQueue.element();
		}else {
			firstNonRepeatingAtIdx+="#";
		}		
	}
	return firstNonRepeatingAtIdx;
}
  	
public static void main(String[] args) {
	/* Test cases provided below: */
	try {
	String stream="aabbccdee";
	System.out.println("Input String: "+stream);
	QueueFirstNonRepeating queueFirstNonRepeating=new QueueFirstNonRepeating();
	String firstNonRepeatingAtIdx=queueFirstNonRepeating.queueFirstNonRepeating(stream);
	System.out.println("Nnrep at idx: "+firstNonRepeatingAtIdx);
	

	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
	
}
	
}