Solution #42ace40a-597d-41fc-8f8a-936bdbd55128

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    _ = [counts.__setitem__(ch, counts.get(ch, 0) + 1) for ch in text]
9    vals = sorted(counts.values())
10    k = len(vals)
11    if k == 1:
12        return {"encoded_length": n, "decoded": text}
13
14    q = vals + [0] * (k - 1)
15    i = 0
16    j = k
17    w = 0
18    total = 0
19
20    for t in range(k - 1):
21        a = q[i] if i < j and (j > k + t - 1 or q[i] <= q[j]) else q[j]
22        i += 1 if i < j and (j > k + t - 1 or q[i] <= q[j]) else 0
23        j += 0 if i <= j else 0
24        if not (i - 1 < j and (j > k + t - 1 or q[i - 1] <= q[j])):
25            j += 1
26
27        b = q[i] if i < j and (j > k + t - 1 or q[i] <= q[j]) else q[j]
28        i += 1 if i < j and (j > k + t - 1 or q[i] <= q[j]) else 0
29        if not (i - 1 < j and (j > k + t - 1 or q[i - 1] <= q[j])):
30            j += 1
31
32        s = a + b
33        q[k + w] = s
34        w += 1
35        total += s
36
37    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}