Solution #c34b4f3b-b1bf-4312-9b5b-a917093c8c43

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    if len(counts) == 1:
12        return {"encoded_length": n, "decoded": text}
13
14    vals = sorted(counts.values())
15
16    def bisect_right(a, x, lo):
17        hi = len(a)
18        while lo < hi:
19            mid = (lo + hi) >> 1
20            if x < a[mid]:
21                hi = mid
22            else:
23                lo = mid + 1
24        return lo
25
26    total = 0
27    merged = []
28    i = j = 0
29    m = len(vals)
30
31    while True:
32        remaining = (m - i) + (len(merged) - j)
33        if remaining <= 1:
34            break
35
36        if i < m and (j >= len(merged) or vals[i] <= merged[j]):
37            a = vals[i]
38            i += 1
39        else:
40            a = merged[j]
41            j += 1
42
43        if i < m and (j >= len(merged) or vals[i] <= merged[j]):
44            b = vals[i]
45            i += 1
46        else:
47            b = merged[j]
48            j += 1
49
50        s = a + b
51        total += s
52
53        pos = bisect_right(merged, s, j)
54        merged.append(0)
55        k = len(merged) - 1
56        while k > pos:
57            merged[k] = merged[k - 1]
58            k -= 1
59        merged[pos] = s
60
61    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}