Solution #917a89f1-b1b0-4947-9dde-152b287ea4f8

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    # In-place binary min-heap over frequencies using a single growing list.
15    heap = []
16    push = heap.append
17    for v in counts.values():
18        push(v)
19
20    # Heapify
21    i = (len(heap) >> 1) - 1
22    while i >= 0:
23        j = i
24        x = heap[j]
25        size = len(heap)
26        while True:
27            l = (j << 1) + 1
28            if l >= size:
29                break
30            r = l + 1
31            c = l
32            if r < size and heap[r] < heap[l]:
33                c = r
34            y = heap[c]
35            if x <= y:
36                break
37            heap[j] = y
38            j = c
39        heap[j] = x
40        i -= 1
41
42    total = 0
43
44    while len(heap) > 1:
45        size = len(heap)
46
47        a = heap[0]
48        x = heap[size - 1]
49        if size == 2:
50            heap.pop()
51        else:
52            heap[0] = x
53            heap.pop()
54            size -= 1
55            j = 0
56            while True:
57                l = (j << 1) + 1
58                if l >= size:
59                    break
60                r = l + 1
61                c = l
62                if r < size and heap[r] < heap[l]:
63                    c = r
64                y = heap[c]
65                if x <= y:
66                    break
67                heap[j] = y
68                j = c
69            heap[j] = x
70
71        size = len(heap)
72        b = heap[0]
73        x = heap[size - 1]
74        if size == 2:
75            heap.pop()
76        else:
77            heap[0] = x
78            heap.pop()
79            size -= 1
80            j = 0
81            while True:
82                l = (j << 1) + 1
83                if l >= size:
84                    break
85                r = l + 1
86                c = l
87                if r < size and heap[r] < heap[l]:
88                    c = r
89                y = heap[c]
90                if x <= y:
91                    break
92                heap[j] = y
93                j = c
94            heap[j] = x
95
96        s = a + b
97        total += s
98
99        heap.append(s)
100        j = len(heap) - 1
101        while j:
102            p = (j - 1) >> 1
103            y = heap[p]
104            if y <= s:
105                break
106            heap[j] = y
107            j = p
108        heap[j] = s
109
110    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}