Solution #76aeaf5e-0029-44ff-8c0e-51a655a58d90

def solve(input):
    text = input.get("text", "")
    n = len(text)
    if n == 0:
        return {"encoded_length": 0, "decoded": ""}

    counts = {}
    get = counts.get
    for ch in text:
        counts[ch] = get(ch, 0) + 1

    freqs = list(counts.values())
    m = len(freqs)

    if m == 1:
        return {"encoded_length": n, "decoded": text}

    freqs.sort()

    # Bottom-up two-queue Huffman merge:
    # use freqs as first queue and merged as second queue.
    merged = [0] * (m - 1)
    i = j = k = 0
    total = 0

    while k < m - 1:
        if i < m and (j >= k or freqs[i] <= merged[j]):
            a = freqs[i]
            i += 1
        else:
            a = merged[j]
            j += 1

        if i < m and (j >= k or freqs[i] <= merged[j]):
            b = freqs[i]
            i += 1
        else:
            b = merged[j]
            j += 1

        s = a + b
        merged[k] = s
        total += s
        k += 1

    return {"encoded_length": total, "decoded": text}