Solution #4911088c-d5f3-458e-891b-4b2c402c62dc

1def solve(input):
2    text = input.get("text", "")
3    n = len(text)
4    if not n:
5        return {"encoded_length": 0, "decoded": ""}
6
7    class Node:
8        __slots__ = ("w", "left", "right")
9        def __init__(self, w, left=-1, right=-1):
10            self.w = w
11            self.left = left
12            self.right = right
13
14    counts = {}
15    get = counts.get
16    for ch in text:
17        counts[ch] = get(ch, 0) + 1
18
19    m = len(counts)
20    if m == 1:
21        return {"encoded_length": n, "decoded": text}
22
23    nodes = []
24    append = nodes.append
25    for w in counts.values():
26        append(Node(w))
27
28    order = sorted(range(m), key=lambda i: nodes[i].w)
29
30    q1 = order
31    q2 = [0] * (m - 1)
32    h1 = 0
33    t1 = m
34    h2 = 0
35    t2 = 0
36    next_idx = m
37
38    def pop_min():
39        nonlocal h1, h2
40        if h1 < t1:
41            if h2 < t2 and nodes[q2[h2]].w < nodes[q1[h1]].w:
42                idx = q2[h2]
43                h2 += 1
44                return idx
45            idx = q1[h1]
46            h1 += 1
47            return idx
48        idx = q2[h2]
49        h2 += 1
50        return idx
51
52    for _ in range(m - 1):
53        a = pop_min()
54        b = pop_min()
55        w = nodes[a].w + nodes[b].w
56        append(Node(w, a, b))
57        q2[t2] = next_idx
58        t2 += 1
59        next_idx += 1
60
61    total = 0
62    stack = [(next_idx - 1, 0)]
63    pop = stack.pop
64    push = stack.append
65    while stack:
66        idx, d = pop()
67        node = nodes[idx]
68        left = node.left
69        if left == -1:
70            total += node.w * d
71        else:
72            nd = d + 1
73            push((left, nd))
74            push((node.right, nd))
75
76    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}