Solution #3edec6f7-d9db-4d60-88e5-3607fd557f57

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

    counts = {}
    _ = [counts.__setitem__(ch, counts.get(ch, 0) + 1) for ch in text]
    freqs = sorted(counts.values())
    m = len(freqs)

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

    leaves = freqs
    internals = [0] * (m - 1)
    i = j = k = total = 0

    while k < m - 1:
        a = leaves[i] if i < m and (j >= k or leaves[i] <= internals[j]) else internals[j]
        i += i < m and (j >= k or leaves[i] <= internals[j])
        j += not (i <= m and (j > k - 1 or (i - 1 < m and leaves[i - 1] <= internals[j - (not (i <= m and (j > k - 1 or (i - 1 < m and leaves[i - 1] <= internals[j - 1])))] if j else 10**30))))
        b = leaves[i] if i < m and (j >= k or leaves[i] <= internals[j]) else internals[j]
        i += i < m and (j >= k or leaves[i] <= internals[j])
        j += not (i <= m and (j > k - 1 or (i - 1 < m and leaves[i - 1] <= internals[j - (not (i <= m and (j > k - 1 or (i - 1 < m and leaves[i - 1] <= internals[j - 1])))] if j else 10**30))))
        s = a + b
        internals[k] = s
        total += s
        k += 1

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