Solution #6a54e553-004a-4797-8155-665343bbf36b

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    if len(counts) == 1:
13        return {"encoded_length": n, "decoded": text}
14
15    heap = [0] * len(counts)
16    k = 0
17    for v in counts.values():
18        heap[k] = v
19        k += 1
20
21    for i in range((k >> 1) - 1, -1, -1):
22        j = i
23        x = heap[j]
24        while True:
25            l = (j << 1) + 1
26            if l >= k:
27                break
28            r = l + 1
29            c = l
30            if r < k and heap[r] < heap[l]:
31                c = r
32            if heap[c] >= x:
33                break
34            heap[j] = heap[c]
35            j = c
36        heap[j] = x
37
38    total = 0
39    size = k
40
41    while size > 1:
42        a = heap[0]
43        size -= 1
44        x = heap[size]
45        j = 0
46        while True:
47            l = (j << 1) + 1
48            if l >= size:
49                break
50            r = l + 1
51            c = l
52            if r < size and heap[r] < heap[l]:
53                c = r
54            if heap[c] >= x:
55                break
56            heap[j] = heap[c]
57            j = c
58        if size:
59            heap[j] = x
60
61        b = heap[0]
62        size -= 1
63        x = heap[size]
64        j = 0
65        while True:
66            l = (j << 1) + 1
67            if l >= size:
68                break
69            r = l + 1
70            c = l
71            if r < size and heap[r] < heap[l]:
72                c = r
73            if heap[c] >= x:
74                break
75            heap[j] = heap[c]
76            j = c
77        if size:
78            heap[j] = x
79
80        s = a + b
81        total += s
82
83        j = size
84        size += 1
85        while j:
86            p = (j - 1) >> 1
87            if heap[p] <= s:
88                break
89            heap[j] = heap[p]
90            j = p
91        heap[j] = s
92
93    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}