Solution #40369b8a-64e4-407f-a240-12b85000b84a

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    if len(counts) <= 2:
13        return {"encoded_length": n, "decoded": text}
14
15    heap = {}
16    size = 0
17
18    for f in counts.values():
19        i = size
20        size += 1
21        while i:
22            p = (i - 1) >> 1
23            pv = heap[p]
24            if pv <= f:
25                break
26            heap[i] = pv
27            i = p
28        heap[i] = f
29
30    total = 0
31
32    while size > 1:
33        x = heap[0]
34        size -= 1
35        if size:
36            v = heap[size]
37            i = 0
38            h = size >> 1
39            while i < h:
40                l = (i << 1) + 1
41                r = l + 1
42                c = l
43                cv = heap[l]
44                if r < size:
45                    rv = heap[r]
46                    if rv < cv:
47                        c = r
48                        cv = rv
49                if v <= cv:
50                    break
51                heap[i] = cv
52                i = c
53            heap[i] = v
54
55        y = heap[0]
56        size -= 1
57        if size:
58            v = heap[size]
59            i = 0
60            h = size >> 1
61            while i < h:
62                l = (i << 1) + 1
63                r = l + 1
64                c = l
65                cv = heap[l]
66                if r < size:
67                    rv = heap[r]
68                    if rv < cv:
69                        c = r
70                        cv = rv
71                if v <= cv:
72                    break
73                heap[i] = cv
74                i = c
75            heap[i] = v
76
77        s = x + y
78        total += s
79
80        i = size
81        size += 1
82        while i:
83            p = (i - 1) >> 1
84            pv = heap[p]
85            if pv <= s:
86                break
87            heap[i] = pv
88            i = p
89        heap[i] = s
90
91    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}