Rearrange Characters in String With No Adjacent Duplicate Characters - Algorithms and Problem SolvingAlgorithms and Problem Solving

Rearrange Characters in String With No Adjacent Duplicate Characters - Algorithms and Problem SolvingAlgorithms and Problem Solving

Rearrange Characters in String With No Adjacent Duplicate Characters

Posted on October 29, 2015 by জাহিদ

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.

Read full article from Rearrange Characters in String With No Adjacent Duplicate Characters - Algorithms and Problem SolvingAlgorithms and Problem Solving