Solution #f9d7018b-4fd9-4d38-a260-8e9800fb243d

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    for ch in text:
9        counts[ch] = counts.get(ch, 0) + 1
10
11    freqs = list(counts.values())
12    m = len(freqs)
13
14    if m == 1:
15        return {"encoded_length": n, "decoded": text}
16    if m == 2:
17        return {"encoded_length": n, "decoded": text}
18
19    buckets = [0] * (n + 1)
20    for f in freqs:
21        buckets[f] += 1
22
23    q1 = [0] * m
24    t = 0
25    for f in range(1, n + 1):
26        c = buckets[f]
27        while c:
28            q1[t] = f
29            t += 1
30            c -= 1
31
32    q2 = [0] * (m - 1)
33    i = j = k = 0
34    total = 0
35
36    while k < m - 1:
37        if i < m and (j >= k or q1[i] <= q2[j]):
38            a = q1[i]
39            i += 1
40        else:
41            a = q2[j]
42            j += 1
43
44        if i < m and (j >= k or q1[i] <= q2[j]):
45            b = q1[i]
46            i += 1
47        else:
48            b = q2[j]
49            j += 1
50
51        s = a + b
52        q2[k] = s
53        total += s
54        k += 1
55
56    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}