Solution #06ab1c25-28af-4434-8eff-fb20d9e0838f

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    vals = tuple(counts.values())
13    if len(vals) == 1:
14        return {"encoded_length": n, "decoded": text}
15
16    s = ",".join(map(str, vals))
17    nums = sorted(map(int, s.split(",")))
18
19    i = 0
20    j = 0
21    q = ""
22    qlen = 0
23    total = 0
24    m = len(nums)
25
26    def take():
27        nonlocal i, j, q, qlen
28        if i < m:
29            if j < qlen:
30                k = q.find(",", j)
31                qv = int(q[j:k])
32                if nums[i] <= qv:
33                    v = nums[i]
34                    i += 1
35                    return v
36                j = k + 1
37                return qv
38            v = nums[i]
39            i += 1
40            return v
41        k = q.find(",", j)
42        v = int(q[j:k])
43        j = k + 1
44        return v
45
46    while (m - i) + (qlen - j) // 2 > 1:
47        a = take()
48        b = take()
49        s2 = a + b
50        total += s2
51        q += str(s2) + ","
52        qlen = len(q)
53
54    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}