Learn-dsa..in 30 days!



























CC-14 : Rearrange characters of String so that none of the duplicate characters occur together in the rearranged String.

Description:

Given a String as input, convert it into a Max Heap, rearrange characters of String so that none of the duplicate characters occur together in the rearranged String.

Test cases and expected outputs:

Input Parameters Expected outputs
Original String: prettier Rearranged String: retretpi
Original String: good Rearranged String: odgo
Original String: redder Rearranged String: redred

Pseudocode:

Class CharCount:

Create an internal class CharCount.
We will extract characters from input String and for each individual character, the instances of CharCount will hold reference to the character and count of frequency of the character within the String.

Class SortByFreq:

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

Method rearrange(str):

This method takes input String as parameter.
Initialize a HashMap named freq 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 SortByFreq to the constructor the PriorityQueue to sort by frequency of occurrence of characters.
Iterate through keys of hashMap freq:
Add the current key (char) to heap. The comparator provided to heap, automatically extracts the frequency corresponding to current key from hashMap and adds integer to heap as per required heap’s index sorting order.
Initialize a StringBuilder instance named rearranged to collate the rearranged characters.
Initialize a CharCount instance named prevChar to store the previous character that was processed. Initially, set prevChar.c to ‘#’ and prevChar.Freq to -1.
While heapsize is not 0:
Remove a CharCount instance named charCount from top of heap and append the character contained within the same to rearranged.
If prevChar.Freq > 0 add it to the heap.
Reduce charCount.Freq by 1 as we have processed one character in current iteration.
Set prevChar to charCount.
Return rearranged.toString().

Code:

public class HeapRearrangeString {
	
class CharCount{
	char c;
	int freq;
}

class SortByFreq implements Comparator<CharCount> {
	public int compare(CharCount c1, CharCount c2) {
		if (c1.freq < c2.freq) {return 1;}
		if (c1.freq > c2.freq) {return -1;}
		return 0;
	}	
}
 
public String rearrange(String str) {
	HashMap<Character,Integer> freq=new HashMap<Character,Integer>();
	char[] chars=str.toCharArray();
	for (int idx=0; idx < chars.length; idx++) {
		int currFreq=freq.getOrDefault(chars[idx],0);
		freq.put(chars[idx], currFreq+1);
	}	
	PriorityQueue<CharCount> heap=new PriorityQueue<CharCount>(new SortByFreq());
	Iterator< Map.Entry< Character,Integer > > itr=freq.entrySet().iterator();
	while (itr.hasNext()) {
		Map.Entry<Character,Integer> entry=itr.next();
		CharCount charCount=new CharCount();
		charCount.c=entry.getKey();
		charCount.freq=entry.getValue();
		heap.add(charCount);
	}
	StringBuilder rearranged=new StringBuilder();
	CharCount prevChar=new CharCount();
	prevChar.c='#';
	prevChar.freq=-1;
    while(heap.size() != 0) {
		CharCount charCount=heap.remove();
		rearranged.append(charCount.c);
		if (prevChar.freq > 0) {
			heap.add(prevChar);
		}
		charCount.freq--;
		prevChar=charCount;		
	}
    if (rearranged.length()!= str.length()) {
    	return "";
    }		
	return rearranged.toString();
}
}

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us