Rearrange characters in a string such that no two adjacent characters are same. Given a string with lowercase repeated characters, the task is to rearrange characters in a string so that no two adjacent characters are the same. If it is not possible to do so, then print “Not possible”.
The idea is to put the highest frequency character first (a greedy approach). Use a priority queue(or binary max heap)and put all characters and ordered by their frequencies(highest frequency character at root). one by one take the highest frequency character from the heap and add it to result. After adding it, just decrease the frequency of the character and then temporarily move this character out of priority queue so that it is not picked again next time.
while priority queue is not empty. pop an element and add it to the result. Decrease the frequency of the popped element by ‘1’ . push the previous element back in to the priority_queue if its frequency is greater than zero. make the current element as the previous elements for the next iteration.
If the length of the resultant string and the original string is not equal, then print "not possible", else print the resultant string.