Problem:

Huffman Coding

We want to encode a given string $S$ to a binary string. Each alphabet character in $S$ should be mapped to a different variable-length code and the code must not be a prefix of others.

Huffman coding is known as one of ways to obtain a code table for such encoding.

For example, we consider that appearance frequencycies of each alphabet character in $S$ are as follows:

  
abcdef

  
freq.4513121695

  
code010110011111011100

We can obtain "Huffman codes" (the third row of the table) using Huffman's algorithm.

The algorithm finds a full binary tree called "Huffman tree" as shown in the following figure.

  

To obtain a Huffman tree, for each alphabet character, we first prepare a node which has no parents and a frequency (weight) of the alphabet character. Then, we repeat the following steps:

  
Choose two nodes, $x$ and $y$, which has no parents and the smallest weights.

  
Create a new node $z$ whose weight is the sum of $x$'s and $y$'s.

  
Add edge linking $z$ to $x$ with label $0$ and to $y$ with label $1$. Then $z$ become their parent.

  
If there is only one node without a parent, which is the root, finish the algorithm. Otherwise, go to step 1.

Finally, we can find a "Huffman code" in a path from the root to leaves.

Task

Given a string $S$, output the length of a binary string obtained by using Huffman coding for $S$.

Input

$S$

A string $S$ is given in a line.

Output

Print the length of a binary string in a line.

Constraints

  
$1 \le |S| \le 10^5$

  
$S$ consists of lowercase English letters.

Sample Input 1

abca

Sample Output 1

6

Sample Input 2

aaabbcccdeeeffg

Sample Output 2

41

Sample Input 3

z

Sample Output 3

1



Sample input:
abca


Sample output:
6

Submission status: Accepted

Solution code:
# ハフマン符号
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/15/ALDS1_15_D

from collections import Counter
import heapq


class Node:
    def __init__(self, count, val=None, left=None, right=None):
        self.val = val
        self.count = count
        self.left = left
        self.right = right

    def __lt__(self, other):
        return self.count < other.count


class HuffmanCoding:
    def __init__(self, s: str):
        self.s = s
        self.counts = Counter(s).most_common()
        self.root = self.build_tree()
        self.encode_table = self.gen_encode_table()

    def build_tree(self):
        hq = list()
        for val, cnt in self.counts:
            heapq.heappush(hq, Node(cnt, val))
        while len(hq) > 1:
            x = heapq.heappop(hq)
            y = heapq.heappop(hq)
            cnt = x.count + y.count
            z = Node(cnt, None, y, x)
            heapq.heappush(hq, z)
        if hq:
            return heapq.heappop(hq)
        else:
            return None

    def gen_encode_table(self):
        encode_table = {}

        def traversal(node, key):
            if node.val:
                if key == "":
                    key = "0"
                encode_table[node.val] = key
            else:
                if node.left:
                    traversal(node.left, key + "1")
                if node.right:
                    traversal(node.right, key + "0")
        key = ""
        if self.root:
            traversal(self.root, key)

        return encode_table

    def get_encode_size(self):
        size = 0
        for a in self.s:
            size += len(self.encode_table[a])
        return size

    def gen_encode_bin(self):
        enc = ""
        for a in self.s:
            enc += self.encode_table[a]
        return enc


def main():
    S = input().strip()
    huffman = HuffmanCoding(S)
    print(huffman.get_encode_size())


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter, deque
from heapq import heappush, heappop, heapify
C = Counter(input())
N = len(C)

if N == 1:
    print(sum(C.values()))
    exit(0)
    
G = [0] * (N * 2)

G[:N] = C
que = [(v, i) for i, v in enumerate(C.values())]
heapify(que)

cur = len(C)
while len(que) > 1:
    v0, nd0 = heappop(que)
    v1, nd1 = heappop(que)
    G[cur]  = (nd0, nd1)
    heappush(que, (v0 + v1, cur))
    cur += 1
root = que[0][1]

ans = 0
que = deque([(0, root)])
while que:
    d, nd = que.popleft()
    if nd < N:
        ans += d * C[G[nd]]
        continue
    u, v = G[nd]
    
    que.append((d + 1, u))
    que.append((d + 1, v))
print(ans)

Submission status: Accepted

Solution code:
import sys, collections, heapq
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    S = SS()

    # ハフマン木の構成
    cnt = collections.Counter(S)
    # (頻度, 文字, 左の子, 右の子)
    freq = [(v, k, None, None) for k, v in cnt.items()]
    heapq.heapify(freq)
    while len(freq) >= 2:
        l = heapq.heappop(freq)
        r = heapq.heappop(freq)
        heapq.heappush(freq, (l[0]+r[0], '', l, r))
    root = heapq.heappop(freq)

    # 符号長の導出
    code_len = {}
    for i in cnt.keys():
        code_len[i] = 1

    def dfs(node, depth):
        if node[1]:
            if depth == 0:
                code_len[node[1]] = 1
            else:
                code_len[node[1]] = depth
        else:
            dfs(node[2], depth+1)
            dfs(node[3], depth+1)

    dfs(root, 0)

    # 符号の長さの計算
    # print(code_len)
    ans = 0
    for i in S:
        ans += code_len[i]
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import heapq

code_list = dict()

class Node():
    def __init__(self, alphabet, rate):
        self.alphabet = alphabet
        self.rate = rate
        self.left = None
        self.right = None

def create_code(node, target, code):
    
    if node == None:
        return 

    if node.alphabet == target:
        code_list[target] = code
        return
        
    create_code(node.left, target, code + "0")
    create_code(node.right, target, code + "1")

def Main():
    S = input().replace("\n", "")
    N = len(S)

    node_list = list()
    count_list = dict()

    character = set(S)
    character = sorted(character)

    for c in character:
        count = S.count(c)
        count_list[c] = count
        n = Node(c, float(count/N))
        node_list.append(n)

    huf_tree = None

    if len(node_list) == 1:
        n1 = node_list.pop()
        new = Node("", n1.rate)
        new.left = n1

        huf_tree = new

    else:
        while len(node_list) >= 2:
            node_list.sort(key = lambda x : x.rate, reverse = True)

            n1 = node_list.pop()
            n2 = node_list.pop()

            new = Node("", n1.rate + n2.rate)
            new.left = n1
            new.right = n2
            node_list.append(new)

            huf_tree = new

    code_length = 0

    for c in character:
        create_code(huf_tree, c, "")
        code_length += len(code_list[c]) * count_list[c]

    print(code_length)

Main()

Submission status: Accepted

Solution code:
from collections import Counter

S=input()
freq=sorted(list(dict(Counter(S)).items()),key=lambda w:w[1])
length={chr(ord('a')+i):0 for i in range(26)}
while len(freq)>1:
    minimum1=freq.pop(0)
    minimum2=freq.pop(0)
    for c in minimum1[0]+minimum2[0]:
        length[c]=length[c]+1
    freq.append((minimum1[0]+minimum2[0],minimum1[1]+minimum2[1]))
    freq=sorted(freq,key=lambda w:w[1])

retval=0
for s in S:
    retval+=max(length[s],1)
print(retval)

Submission status: Accepted

Solution code:
import heapq

class Node:
    def __init__(self, k, v):
        self.k = k
        self.v = v
        self.left = None
        self.right = None

def hist(s):
    d = {}
    for c in s:
        if c not in d:
            d[c] = 0
        d[c] += 1
    return d

S = raw_input()
D = hist(S)
pool = []
for k,v in D.items():
    heapq.heappush(pool, (v, Node(k,v)))

while len(pool) >= 2:
    _, x = heapq.heappop(pool)
    _, y = heapq.heappop(pool)
    zv = x.v + y.v
    z = Node("", zv)

    if x.v > y.v and x.k != "":
        x,y = y,x
    z.left = x
    z.right = y
    heapq.heappush(pool, (zv,z))

D = {}
def traverse(node, code):
    if node.k == "":
        traverse(node.right, code+"1")
        traverse(node.left, code+"0")
    else:
        if code == "":
            code += "0"
        D[node.k] = code

traverse(pool[0][1], "")
#print D
ans = sum([len(D[c]) for c in S])
print ans

Submission status: Accepted

Solution code:
from typing import Dict


class Node():
    left = None
    right = None
    parent = None
    char = ''
    value = 0

    def __init__(self, char: str = '', value: int = 0) -> None:
        self.char = char
        self.value = value


def get_coded_str_len(node: Node, base_str: str) -> int:
    if node.char:
        # Return the length of the coded string.
        return len(base_str) * node.value
    else:
        coded_str_len = 0
        if node.left:
            coded_str_len += get_coded_str_len(node.left, base_str + '0')
        if node.right:
            coded_str_len += get_coded_str_len(node.right, base_str + '1')
        return coded_str_len


if __name__ == "__main__":
    input_str = input()
    char_dict: Dict[str, int] = {}
    for s in input_str:
        if s in char_dict:
            char_dict[s] += 1
        else:
            char_dict[s] = 1

    nodes = [Node(char=k, value=v) for k, v in char_dict.items()]
    # Sort in the ascending order.
    nodes.sort(key=lambda x: x.value)

    if 1 == len(nodes):
        node = Node()
        node.left = nodes.pop(0)  # type: ignore
        nodes.append(node)
    else:
        while 1 != len(nodes):
            node = Node()
            node.left = nodes.pop(0)  # type: ignore
            node.right = nodes.pop(0)  # type: ignore
            node.value = node.left.value + node.right.value  # type: ignore
            nodes.append(node)
            # Sort in the ascending order.
            nodes.sort(key=lambda x: x.value)

    print(f"{get_coded_str_len(nodes[0], '')}")

Submission status: Accepted

Solution code:
import heapq

S = input()

# 数え上げ
chars = [[0, n] for n in range(256)]
for s in S:
	chars[ord(s)][0] += 1

# ハフマン木生成
# ：ノードの構造：[count, char, left=None, right=None]
# ：[1]のcharは、heapqでユニークキーとして機能するように追加した
counts = []
for char in chars:
	if not char[0]:
		continue
	heapq.heappush(counts, [char[0], char[1], None, None, char])

# ハフマン木編成
while 1 < len(counts):
	a, b = heapq.heappop(counts), heapq.heappop(counts)
	heapq.heappush(counts, [a[0] + b[0], -1, a, b])
root = heapq.heappop(counts)

# コード化(左：0、右：1)
codes = {};
def dfs(node, code):
	# 節の処理
	if node[1] < 0:
		dfs(node[2], code + "0")
		dfs(node[3], code + "1")
		return
	# 葉の処理
	codes[chr(node[1])] = code
dfs(root, "")

# 集計
count = 0
for s in S:
	count += len(codes[s])

# 1種類の場合のみ例外処理…いずれなんとか
if 1 == len(set(S)):
	print(len(S))
else:
	print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Greedy algorithms - Huffman Coding
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_15_D&lang=jp

"""
import sys
from collections import Counter

class Node:
    def __init__(self, v, f):
        self.val = v
        self.freq = f
        self.left = None
        self.right = None


def solve(s):
    res = [Node(k, v) for k, v in Counter(s).items()]
    while len(res) > 1:
        res.sort(key=lambda x: x.freq)
        z = Node('@', res[0].freq + res[1].freq)
        z.left, z.right = res[0], res[1]
        res = res[2:]
        res.append(z)

    d = dict()
    stack = [(res[0], '')]
    while stack:
        n, st = stack.pop()
        if not n.left and not n.right:
            st = '0' if not st else st
            d[n.val] = st
        if n.left:
            stack.append((n.left, st+'0'))
        if n.right:
            stack.append((n.right, st+'1'))
    return len(''.join([d[ch] for ch in s]))


def main(args):
    s = input()
    ans = solve(s)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
S = input()


dict_string = {}
dict_depth = {}

for s in S:
    if s in dict_string:
        dict_string[s] += 1
    else:
        dict_string[s] = 1
        dict_depth[s] = 0


dict_string_calc = dict_string.copy()


while len(dict_string_calc) != 1:
    x = None
    y = None

    for k, v in sorted(dict_string_calc.items(), key=lambda x: x[1]):
        if x == None:
            x = k
            x_cnt = v
            continue

        if y == None:
            y = k
            y_cnt = v
            break

    for s in (x + y):
        if s in dict_depth:
            dict_depth[s] += 1
        else:
            raise

    del dict_string_calc[x]
    del dict_string_calc[y]

    dict_string_calc[x + y] = x_cnt + y_cnt


ans = 0

for k, v in dict_depth.items():
    ans += dict_string[k] * v


if len(dict_string) == 1:
    ans = len(S)

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
from collections import Counter


class Node:
    
    def __init__(self, weight):
        self.weight = weight
    
    def set_parent(self,parent):
        self.parent = parent
        
    def get_length(self):
        try:
            tmp = 1 + self.parent.get_length()
        except AttributeError:
            tmp = 0
        return tmp
        
    def get_weight(self):
        return self.weight

    def __lt__(self, other):
        return self.weight < other.weight
    

S = input()
d = Counter(S)
tree_dic = {}
h = []
num = 0
for i in d:
    tree_dic[i] = Node(d[i])
    heappush(h,tree_dic[i])
while(len(h) > 1):
    tmp0 = heappop(h)
    tmp1 = heappop(h)
    tree_dic[num] = Node(tmp0.get_weight() + tmp1.get_weight())
    tmp0.set_parent(tree_dic[num])
    tmp1.set_parent(tree_dic[num])
    heappush(h,tree_dic[num])
    num+=1

ans = 0
for i in S:
    ans += tree_dic[i].get_length()
if len(S) == 1:
    print(1)
elif len(d) == 1:
    print(len(S))
else:
    print(ans)

Submission status: Accepted

Solution code:
from heapq import *
class Node():
    def __init__(self, key, char=None):
        self.key = key
        self.char = char
        self.pare = None

st = input()
_st = list(set(st))

a = []
for i in _st:
    a  += [(st.count(i),i)] 
heapify(a)

node = {}
for i in range(len(a)):
    cnt, char = a[i]
    node[char] = Node(cnt, char)

while len(a) > 1:
    p1, p2 = heappop(a)
    q1, q2 = heappop(a)
    x = Node(p1+q1, p2+q2) 
    node[p2+q2] = x
    if len(a) == 0:
        root = x
        break
    node[p2].pare = x
    node[q2].pare = x
    heappush(a, (p1+q1,p2+q2))

def dfs(node, cnt=1):
    if node.pare == None:
        return cnt
    a = dfs(node.pare, cnt+1)
    return a

Sum = 0
for i in _st:
    no = node[i]
    depth = dfs(no)
    Sum += depth*no.key
    
print(Sum)

Submission status: Accepted

Solution code:
import heapq
from collections import Counter


class HuffmanTreeNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None
    
    def __lt__(self, other):
        return self.freq < other.freq


def huffman_code_helper(root, code='', codes={}):
    if not root:
        return codes
    
    if not root.left and not root.right:
        codes[root.char] = code if code else '0'
        return codes
    
    huffman_code_helper(root.left, code + '0', codes)
    huffman_code_helper(root.right, code + '1', codes)
    return codes


def huffman_code(text):
    counter = Counter(text)
    heap = []
    for char, freq in counter.items():
        heap.append(HuffmanTreeNode(char, freq))
    heapq.heapify(heap)

    while len(heap) > 1:
        left, right = heapq.heappop(heap), heapq.heappop(heap)
        node = HuffmanTreeNode('', left.freq + right.freq)
        node.left, node.right = left, right
        heapq.heappush(heap, node)
    root = heap[0]

    return huffman_code_helper(root)


def solution():
    text = input()
    codes = huffman_code(text)
    encoded = []
    for char in text:
        encoded.append(codes[char])
    print(len(''.join(encoded)))

solution()

Submission status: Accepted

Solution code:
class Node():
    p = None
    l = None
    r = None
    char = ''
    count = 0

    def __init__(self, char='', count=0):
        self.char = char
        self.count = count


def solve(n, h):
    if n.char:
        # print('{}:{}'.format(n.char, h))
        return len(h) * n.count
    else:
        ret = 0
        if n.l: ret += solve(n.l, h + '0')
        if n.r: ret += solve(n.r, h + '1')
        return ret


# --------------------
S = input()
C = {}
T = []

for s in S:
    C.setdefault(s, 0)
    C[s] += 1

T = [Node(*x) for x in C.items()]
T.sort(key=lambda x: x.count)

if len(T) == 1:
    n = Node()
    n.l = T.pop(0)
    T.append(n)
else:
    while len(T) != 1:
        n = Node()
        n.l = T.pop(0)
        n.r = T.pop(0)
        n.count = n.l.count + n.r.count
        T.append(n)
        T.sort(key=lambda x: x.count)

print(solve(T[0], ''))

Submission status: Accepted

Solution code:
from collections import Counter, deque
from heapq import heappush, heappop, heapify
C = Counter(input())
N = len(C)

if N == 1:
    print(sum(C.values()))
    exit(0)

G = [0]*(N*2)

G[:N] = C
que = [(v, i) for i, v in enumerate(C.values())]
heapify(que)

cur = len(C)
while len(que) > 1:
    v0, nd0 = heappop(que)
    v1, nd1 = heappop(que)
    G[cur] = (nd0, nd1)
    heappush(que, (v0+v1, cur))
    cur += 1
root = que[0][1]

ans = 0
que = deque([(0, root)])
while que:
    d, nd = que.popleft()
    if nd < N:
        ans += d * C[G[nd]]
        continue
    u, v = G[nd]

    que.append((d+1, u))
    que.append((d+1, v))
print(ans)