Solution #4b16e427-07d8-4ccb-9d87-fd1e02f4d97b

1def solve(input):
2    text = input.get("text", "")
3    n = len(text)
4    if n == 0:
5        return {"encoded_length": 0, "decoded": ""}
6
7    if n == 1:
8        return {"encoded_length": 1, "decoded": text}
9
10    total = 0
11    # In-place frequency accumulation via sorted run-length encoding.
12    # This avoids a dict and builds the multiset of weights directly.
13    s = sorted(text)
14
15    # Single-symbol case handled via run counting
16    weights = []
17    prev = s[0]
18    cnt = 1
19    for i in range(1, n):
20        ch = s[i]
21        if ch == prev:
22            cnt += 1
23        else:
24            weights.append(cnt)
25            prev = ch
26            cnt = 1
27    weights.append(cnt)
28
29    m = len(weights)
30    if m == 1:
31        return {"encoded_length": n, "decoded": text}
32
33    # weights already sorted because equal chars are grouped in sorted(text)
34    # Two-queue Huffman merge without heap/list reinsertion.
35    merged = [0] * (m - 1)
36    i = 0
37    j = 0
38    k = 0
39
40    def take():
41        nonlocal i, j
42        if i < m and (j >= k or weights[i] <= merged[j]):
43            v = weights[i]
44            i += 1
45            return v
46        v = merged[j]
47        j += 1
48        return v
49
50    while k < m - 1:
51        a = take()
52        b = take()
53        s2 = a + b
54        total += s2
55        merged[k] = s2
56        k += 1
57
58    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}