Solution #d7adae63-4770-4e09-a93f-d69d5169f9f6

1def solve(input):
2    text = input.get("text", "")
3    n = len(text)
4    if n == 0:
5        return {"encoded_length": 0, "decoded": ""}
6
7    from functools import lru_cache
8
9    counts = {}
10    get = counts.get
11    for ch in text:
12        counts[ch] = get(ch, 0) + 1
13
14    if len(counts) == 1:
15        return {"encoded_length": n, "decoded": text}
16
17    freqs = sorted(counts.values())
18    m = len(freqs)
19
20    @lru_cache(None)
21    def merged_weight(i, j):
22        return freqs[i] + freqs[j]
23
24    q1 = 0
25    q2 = 0
26    merged = [0] * (m - 1)
27    made = 0
28    total = 0
29
30    def take_min():
31        nonlocal q1, q2
32        if q1 < m and q2 < made:
33            if freqs[q1] <= merged[q2]:
34                v = freqs[q1]
35                q1 += 1
36                return v
37            v = merged[q2]
38            q2 += 1
39            return v
40        if q1 < m:
41            v = freqs[q1]
42            q1 += 1
43            return v
44        v = merged[q2]
45        q2 += 1
46        return v
47
48    while made < m - 1:
49        a = take_min()
50        b = take_min()
51        s = a + b
52        merged[made] = merged_weight(freqs.index(a) if False else 0, freqs.index(b) if False else 0) if False else s
53        total += s
54        made += 1
55
56    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}