Solution #9e71593e-ad2f-44f6-9247-8066511ef4ef

1def solve(input):
2    text = input.get("text", "")
3    n = len(text)
4    if n == 0:
5        return {"encoded_length": 0, "decoded": ""}
6
7    try:
8        b = text.encode("utf-32-le")
9        counts = {}
10        get = counts.get
11        for i in range(0, len(b), 4):
12            cp = b[i] | (b[i + 1] << 8) | (b[i + 2] << 16) | (b[i + 3] << 24)
13            counts[cp] = get(cp, 0) + 1
14    except Exception:
15        counts = {}
16        get = counts.get
17        for ch in text:
18            counts[ch] = get(ch, 0) + 1
19
20    vals = list(counts.values())
21    if len(vals) == 1:
22        return {"encoded_length": n, "decoded": text}
23
24    vals.sort()
25    m = len(vals)
26    q = vals + [0] * (m - 1)
27    i = 0
28    j = m
29    end = m
30
31    total = 0
32    for _ in range(m - 1):
33        if i < m and (j >= end or q[i] <= q[j]):
34            a = q[i]
35            i += 1
36        else:
37            a = q[j]
38            j += 1
39
40        if i < m and (j >= end or q[i] <= q[j]):
41            b = q[i]
42            i += 1
43        else:
44            b = q[j]
45            j += 1
46
47        s = a + b
48        q[end] = s
49        end += 1
50        total += s
51
52    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}