# 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 a 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)

    return most_freq_chars

# 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="")
        print('\tCharacter frequencies as a max-heap: \n\t', reorganize_string(test_cases[i]))
        print("-"*100)


if __name__ == '__main__':
    main()