CC-9 : Find first K non repeating characters.

Description:

Given a String as input, find the first kth non repeating characters within the same.

Test cases and expected outputs:

Input Parameters	Expected outputs
The input String: procession	First 3 non repeating chars: p r c

Pseudocode:

Class CharFreqIndex:

Create an internal class CharFreqIndex

We will extract characters from input String and for each individual character, The instances of CharFreqIndex will hold reference to the character, count of frequency of the character and its last index within the String.

Class SortByIndex:

This class implements Comparator.compare() method. The method takes 2 instance of CharFreqIndex and helps to sort the same by index of the character.

Method findFirstKNonRepeatingChars():

This method takes input String as parameter. We need to find first k non repeating character within input String and value of k is also received as input parameter.

Initialize a HashMap named hashMap which we will use to count the frequency of occurrence of characters in the input String.

Extract the characters from input String and store in character array named chars.

Iterate though chars from index 0 to index chars.length-1:

Check if hashMap already contains chars[idx]. If already present, extract the frequency of the chars[idx] from hashMap. Increment the frequency by 1 and put chars[idx] and the updated frequency back into to the hashMap.

Initialize a PriorityQueue instance named heap. Provide an instance of SortByIndex to the constructor the PriorityQueue to sort by frequency of occurrence of characters.

Iterate through keys of hashMap freq:

If the frequency of current character from iterator is 1, it means it is a non-repeating character.

Add the current key (char) to heap. The comparator provided to heap, automatically extracts the index corresponding to current key from hashMap and adds integer to minheap as per required heap’s index sorting order.

Extract the top k characters from the heap and return then from the method.

Code:

public class HeapFindFirstKNonRepeatingChars {
	
class CharFreqIndex{
	char c;
	int index;
	int freq;
}

class SortByIndex implements Comparator<CharFreqIndex> {
	public int compare(CharFreqIndex c1, CharFreqIndex c2) {
		if (c1.index < c2.index) {return -1;}
		if (c1.index > c2.index) {return 1;}
		return 0;
	}	
}
 
public String findFirstKNonRepeatingChars(String str, int k) {
	HashMap<Character,CharFreqIndex> hashMap=new HashMap<Character,CharFreqIndex>();
	char[] chars=str.toCharArray();
	for (int idx=0; idx < chars.length; idx++) {
		CharFreqIndex curr=hashMap.get(chars[idx]);
		int currFreq=0;
		if (curr !=null) {
			currFreq=curr.freq;
		}
		CharFreqIndex charFreqIndex=new CharFreqIndex();
		charFreqIndex.c=chars[idx];
		charFreqIndex.index=idx;
		charFreqIndex.freq=currFreq+1;		
		hashMap.put(chars[idx], charFreqIndex);		
	}	
	PriorityQueue< CharFreqIndex > heap=new PriorityQueue< CharFreqIndex >(new SortByIndex());
	Iterator< Map.Entry < Character,CharFreqIndex > > itr=hashMap.entrySet().iterator();
	while (itr.hasNext()) {
		Map.Entry<Character,CharFreqIndex> entry=itr.next();
		CharFreqIndex charCount=entry.getValue();
		if (charCount.freq==1) {
			heap.add(charCount);
		}
	}
	StringBuilder nonRepeatedFirstK=new StringBuilder();
	while(k > 0) {
		nonRepeatedFirstK.append(heap.remove().c + " ");
		k--;
	}
	return nonRepeatedFirstK.toString();
}

}

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.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.PriorityQueue;

public class HeapFindFirstKNonRepeatingChars {
	
class CharFreqIndex{
	char c;
	int index;
	int freq;
}

class SortByIndex implements Comparator<CharFreqIndex> {
	public int compare(CharFreqIndex c1, CharFreqIndex c2) {
		if (c1.index < c2.index) {return -1;}
		if (c1.index > c2.index) {return 1;}
		return 0;
	}	
}
 
public String findFirstKNonRepeatingChars(String str, int k) {
	HashMap<Character,CharFreqIndex> hashMap=new HashMap<Character,CharFreqIndex>();
	char[] chars=str.toCharArray();
	for (int idx=0; idx < chars.length; idx++) {
		CharFreqIndex curr=hashMap.get(chars[idx]);
		int currFreq=0;
		if (curr !=null) {
			currFreq=curr.freq;
		}
		CharFreqIndex charFreqIndex=new CharFreqIndex();
		charFreqIndex.c=chars[idx];
		charFreqIndex.index=idx;
		charFreqIndex.freq=currFreq+1;		
		hashMap.put(chars[idx], charFreqIndex);		
	}	
	PriorityQueue< CharFreqIndex > heap=new PriorityQueue< CharFreqIndex >(new SortByIndex());
	Iterator< Map.Entry < Character,CharFreqIndex > > itr=hashMap.entrySet().iterator();
	while (itr.hasNext()) {
		Map.Entry<Character,CharFreqIndex> entry=itr.next();
		CharFreqIndex charCount=entry.getValue();
		if (charCount.freq==1) {
			heap.add(charCount);
		}
	}
	StringBuilder nonRepeatedFirstK=new StringBuilder();
	while(k > 0) {
		nonRepeatedFirstK.append(heap.remove().c + " ");
		k--;
	}
	return nonRepeatedFirstK.toString();
}

public static void main(String[] args) {

String retVal;
try {
	HeapFindFirstKNonRepeatingChars hp=new HeapFindFirstKNonRepeatingChars();
	String str= "procession";
	System.out.println("Original String: "+ str);
	retVal=hp.findFirstKNonRepeatingChars(str, 3);
	System.out.println("First 3 non repeating chars: "+ retVal);
	
	
		
}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}



}