# importing libraries
from collections import Counter
import heapq


def reorganize_string(str):
    # Calculate the frequency of characters in string and store counts
    # of each character along with the character itself in hash map.
    char_counter = Counter(str)

    # initializing heap
    most_freq_chars = []

    # Store character and its negative frequency in the array
    for char, count in char_counter.items():
        most_freq_chars.append([-count, char])

    # Construct heap from the array
    heapq.heapify(most_freq_chars)

    # initializing variables
    previous = None
    result = ""

    while len(most_freq_chars) > 0 or previous:
        count, char = heapq.heappop(most_freq_chars)
        result = result + char
       # decrement the character count, as we've now used one occurrence of it
        count = count + 1   # as we store negative character counts, adding 1 is actually a decrement operation

        # pushing the char back to heap
        if previous:
            heapq.heappush(most_freq_chars, previous)
            previous = None

        # setting previous to the most recent used char
        if count != 0:
            previous = [count, char]

    return result


# Driver code
def main():
    test_cases = ["programming", "hello", "fofjjb",
              "abbacdde", "aba", "awesome"]
    for i in range(len(test_cases)):
        print(i+1, '. \tInput string: "', test_cases[i], '"', sep="")
        temp = reorganize_string(test_cases[i])
        print('\tReorganized string: "', temp + '"' if temp else '"', sep="")
        print("-"*100)


if __name__ == '__main__':
    main()