Rearrange Characters in String With No Adjacent Duplicate Characters

Given a string, rearrange characters of the string such that no duplicate characters are adjacent to each other.

For example,

Input: aaabc
Output: abaca

Input: aa
Output: No valid output

Input: aaaabc
Output: No valid output

How can we achieve this rearrangement? The very first idea that may pop up is to count the frequency of character and then rearrange based on count. However, if more than n/2 elements are sam then there is no such rearrangement because of the simple fact that more than n/2 duplicates will need at least more than n/2 other unique characters to put in between two duplicates.

Thus if there is no character with more than n/2 duplicates then we can potentially rearrange them by putting a different character in between two duplicates. But the other characters may also have duplicates. So, it is hard to pickup a character in greedy fashion. So, how to choose a character to put it in between two other duplicates?

We can find out how many total unique characters are there and what is there frequency. So, we know we need to interleave the most frequent character by another character. What is the best ‘another’ character? The arrangement would be very straightforward if there are only two unique characters , each appearing n/2 times. Then we just interleave one between other (and at the boundary). For example, rearranging aaabbb is as easy as ababab. But what will happen if we have many other repeating characters. Note that, as long as a character is not repeating more than n/2 times, we can always find another character with same or less frequency to interleave the duplicates. The remaining can be interleaved with other characters.

The above discussion throws an idea of taking two top most frequent characters and interleave them as far as possible then take next 2 most frequent and interleave them etc. It is somewhat similar to the Huffman Coding where we take top 2 most frequent characters and merge them into a combined node with summation of frequencies. In our case we similarly take top 2 most frequent characters but instead of merging them we will decrease their frequencies so that we always find two similar frequency characters to interleave with each other.

In order to implement the above idea we can maintain a MaxHeap of character frequency histogram. Each time we try to extract two top most frequent characters and place them in adjacent positions. Then we add those characters back to the heap with decreased frequency (why?). This way we guarantee that the arrangement doesn’t have any two repeating element in adjacent places. The following implementation is based on using PriorityQueue for max heap. Time complexity is O(n) to build the initial heap and O(nlgn) to update the heap for each pair of character realignment.

public static String rearrangeAdjacentDuplicates(String str){
	final class CharFreq implements Comparable<CharFreq>{
		char c;
		int freq;
		public CharFreq(char ch, int count){
			c = ch;
			freq = count;
		}
		@Override
		public int compareTo(CharFreq o) {
			int comp = Double.compare(freq, o.freq);
			if(comp == 0){
				comp = Character.compare(o.c, c);
			}
			
			return comp;
		}
	}
	
	int n = str.length();
	StringBuffer rearranged = new StringBuffer();
	PriorityQueue<CharFreq> maxHeap = new PriorityQueue<CharFreq>(256, Collections.reverseOrder());
	int freqHistoGram[] = new int[256];
	//build the character frequency histogram
	for(char c : str.toCharArray()){
		freqHistoGram[c]++;
		
		//if a character repeats more than n/2 then we can't rearrange
		if(freqHistoGram[c] > (n+1)/2){
			return str;
		}
	}
	//build the max heap of histogram
	for(char i  = 0; i < 256; i++){
		if(freqHistoGram[i] > 0)
			maxHeap.add(new CharFreq(i, freqHistoGram[i]));
	}
	
	//rearrange - pop top 2 most frequent items and arrange them in adjacent positions
	//decrease the histogram frequency of the selected chars 
	while(!maxHeap.isEmpty()){
		//extract top one and decrease the hstogram by one
		CharFreq first = maxHeap.poll();
		rearranged.append(first.c);
		first.freq--;
		
		CharFreq second = null;
		//extract second top and decrease the histogram by one
		if(!maxHeap.isEmpty()){
			second = maxHeap.poll();
			rearranged.append(second.c);
			second.freq--;
		}
		
		//add back the updated histograms 
		if(first.freq > 0){
			maxHeap.add(first);
		}
		if(second != null && second.freq > 0){
			maxHeap.add(second);
		}
	}
	
	return rearranged.toString();
}