LC767

Problem:
Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.Return any possible rearrangement of s or return "" if not possible.

Intuition:
Use least frequent characters to fill the gap between most frequent characters.

Discussion:
The most frequent characters in the previous runs may not be the most frequent characters in later runs because we already place some of them so the frequency decreased thus it may not be the most frequent one any more. We need a data structure that can reflect on that when frequency goes down and to select a new most frequent ones. We can simply sort the list but it takes NlogN time and it’s costly and waste of computing time because we don’t care if rest of elements are sorted or not besides the most frequent one. So this gives us an impression of Heap data structure. The top of the heap is what we want and it only takes logN to maintain the heap property subsequently.

Algorithm: