Solution #e227904f-5ec6-4b63-bdb8-5775a409c53d

1def solve(input):
2    text = input.get("text", "")
3    n = len(text)
4    if not n:
5        return {"encoded_length": 0, "decoded": ""}
6
7    counts = {}
8    get = counts.get
9    for ch in text:
10        counts[ch] = get(ch, 0) + 1
11
12    m = len(counts)
13    if m == 1:
14        return {"encoded_length": n, "decoded": text}
15
16    class Node:
17        __slots__ = ("w", "nxt")
18        def __init__(self, w, nxt=None):
19            self.w = w
20            self.nxt = nxt
21
22    head = None
23    for v in counts.values():
24        head = Node(v, head)
25
26    bins = [None] * (n + 1)
27    cur = head
28    while cur is not None:
29        nxt = cur.nxt
30        w = cur.w
31        cur.nxt = bins[w]
32        bins[w] = cur
33        cur = nxt
34
35    sorted_head = None
36    sorted_tail = None
37    i = 1
38    while i <= n:
39        node = bins[i]
40        while node is not None:
41            nxt = node.nxt
42            node.nxt = None
43            if sorted_head is None:
44                sorted_head = node
45                sorted_tail = node
46            else:
47                sorted_tail.nxt = node
48                sorted_tail = node
49            node = nxt
50        i += 1
51
52    q1 = sorted_head
53    q2 = None
54    q2_tail = None
55    total = 0
56    remaining = m
57
58    while remaining > 1:
59        if q2 is None or (q1 is not None and q1.w <= q2.w):
60            a = q1
61            q1 = q1.nxt
62            wa = a.w
63        else:
64            a = q2
65            q2 = q2.nxt
66            wa = a.w
67
68        if q2 is None or (q1 is not None and q1.w <= q2.w):
69            b = q1
70            q1 = q1.nxt
71            wb = b.w
72        else:
73            b = q2
74            q2 = q2.nxt
75            wb = b.w
76
77        s = wa + wb
78        total += s
79        node = Node(s)
80        if q2 is None:
81            q2 = node
82            q2_tail = node
83        else:
84            q2_tail.nxt = node
85            q2_tail = node
86        remaining -= 1
87
88    return {"encoded_length": total, "decoded": text}

1def solve(input):
2    text = input.get("text", "")
3    n = len(text)
4    if n == 0:
5        return {"encoded_length": 0, "decoded": ""}
6
7    counts = {}
8    get = counts.get
9    for ch in text:
10        counts[ch] = get(ch, 0) + 1
11
12    freqs = list(counts.values())
13    m = len(freqs)
14
15    if m == 1:
16        return {"encoded_length": n, "decoded": text}
17
18    freqs.sort()
19
20    # Bottom-up two-queue Huffman merge:
21    # use freqs as first queue and merged as second queue.
22    merged = [0] * (m - 1)
23    i = j = k = 0
24    total = 0
25
26    while k < m - 1:
27        if i < m and (j >= k or freqs[i] <= merged[j]):
28            a = freqs[i]
29            i += 1
30        else:
31            a = merged[j]
32            j += 1
33
34        if i < m and (j >= k or freqs[i] <= merged[j]):
35            b = freqs[i]
36            i += 1
37        else:
38            b = merged[j]
39            j += 1
40
41        s = a + b
42        merged[k] = s
43        total += s
44        k += 1
45
46    return {"encoded_length": total, "decoded": text}