Learn-dsa..in 30 days!



























CC-2 : Sort characters of String based on Frequency.

Description:

Given String str, sort the characters of str based on the frequency of the characters.

Test cases and expected outputs:

Input Parameters Expected outputs
str="aazzecc" Characters arranged as per increasing frequency are: eacz
str="aazzcc"; Characters arranged as per increasing frequency are: acz
str="azzccccdddd"; Characters arranged as per increasing frequency are: azcd

Pseudocode:

The java method should accept following input parameters: str (String).
Initialize a variable chrFreqMap of type HashMap to hold the input String’s characters and their frequencies.
Iterate through str using a for loop with idx as a loop variable with initial value 0 and increment idx till it reaches str.length-1:
If chrFreqMap does not contain key str.charAt[idx], then put key-value pair str.charAt[idx] and 0 to chrFreqMap.
If chrFreqMap contains key str.charAt[idx] with value freq, then put key-value pair str.charAt[idx] and freq+1 to chrFreqMap.
After completion of above loop, chrFreqMap contains keys that are characters of str and values corresponding to each character key is the frequency of that character in str.
Extract all key value pairs from chrFreqMap and store in Arraylist entriesAl.
Use Collections.sort() method with comparator frqComparator to sort the characters in entriesAl as per their frequency.
After above step, the characters in entriesAl are arranged in order of their frequency. Extract the characters from entriesAl using an iterator and add the same to a StringBuilder sb. Return sb.toString().

Pseudocode for frqComparator():

Collections.sort() method uses a Comparator to compare 2 entries while doing custom sorting.
Create private class frqComparator that implements Comparator interface.
Implement method CompareTo() that takes 2 HashMap entries frstNmOb, scndNmOb from chrFreqMap as input:
Extract the frequency of character from frstNmOb and scndNmOb.
If frequency of character from frstNmOb < frequency of character from scndNmOb return -1.
If frequency of character from frstNmOb = frequency of character from scndNmOb return 0.
If frequency of character from frstNmOb > frequency of character from scndNmOb return 1.

Code:

public String hashMapSortChrByFreq(String str) throws Exception{
	HashMap<Character,Integer> chrFreqMap=new HashMap< Character, Integer >();
	for (int idx=0; idx < str.length(); idx++) {
		chrFreqMap.put(str.charAt(idx), chrFreqMap.getOrDefault(str.charAt(idx),0)+1);
	}		
	
	Set< Map.Entry<Character,Integer>> set=(Set< Entry< Character, Integer>>) chrFreqMap.entrySet();
	ArrayList entriesAl=new ArrayList(set);
	Collections.sort(entriesAl, new frqComparator());
	Iterator< Map.Entry<Character,Integer>> itr=entriesAl.iterator();
	StringBuilder sb=new StringBuilder();
	while(itr.hasNext()) {
		Map.Entry entry=itr.next();
		char c=((Character)((Map.Entry)entry).getKey()).charValue();
		sb.append(c);
	}
	return sb.toString();
}
	
private class frqComparator implements Comparator {
	
public int compare(Object frstNmOb, Object scndNmOb) {
	int frstNm= ((Integer)((Map.Entry)frstNmOb).getValue()).intValue();
	int scndNm= ((Integer)((Map.Entry)scndNmOb).getValue()).intValue();
	int retVal=0;
	if (frstNm < scndNm) {retVal =-1;} else {
		if (frstNm == scndNm) {retVal = 0;} else {
			if (frstNm > scndNm) {retVal = 1;}
		}
	}		
	return retVal;
	}
	
}

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us