from collections import defaultdict
class Node:
    def __init__(self,val, char=None):
        self.val=val
        self.left=None
        self.right=None
        self.code=""
        self.char=char

def bubbleSort(table):
    for i in range (len(table)-1):
        for j in range (i+1, len(table)):
            if(table[i].val>table[j].val):
                t = table[i]
                table[i]=table[j]
                table[j]=t

def createTable(charFreq):
    table=[]
    for key in charFreq:
        table.append(Node(charFreq[key], key))
    return table
        
def createHeap(charFreq):
    table=createTable(charFreq)
    while len(table)>1:
        bubbleSort(table)
        n1,n2=table.pop(0),table.pop(0)
        node = Node(n1.val+n2.val)
        node.left, node.right=n1, n2
        table.append(node)

    return node #this will be the root node

leafNodes=[]
def generateCodes(rootNode):
    global leafNodes
    if rootNode.left and rootNode.right:
        rootNode.left.code=rootNode.code+"0"
        rootNode.right.code=rootNode.code+"1"
        generateCodes(rootNode.left)
        generateCodes(rootNode.right)
    else:
        leafNodes.append(rootNode)
    
print("Enter string:")
text=input()
freqDict=defaultdict(int)

totalBitsBefore=0
for char in text:
    freqDict[char]+=1
    totalBitsBefore+=8

print("Char\tFreq\tCodes\tbit/char\t")
generateCodes(createHeap(freqDict))
totalBitsAfter=0
for node in leafNodes:
    bits=len(node.code)*freqDict[node.char]
    print(node.char,'\t',freqDict[node.char],'\t',node.code,'\t',bits)
    totalBitsAfter+=bits

print("\nTotal before: ",totalBitsBefore,"bits")
print("Total after: ",totalBitsAfter,"bits")
print("Saved: ",totalBitsBefore-totalBitsAfter,"bits")
#aaaaaaaaaaaabbcccccccdddddddddddddeeeeeeeeeeeeeefffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff