Lesson 12

Programming problem.

Given a non-empty string \(s\) of length at most \(10^{4}\), consisting of lowercase Latin letters, construct an optimal prefix-free code. In the first line, output the number of distinct letters \(k\) in the string and the size of the resulting encoded string. In the next \(k\) lines, print the codes of the letters in the format «letter: code». In the last line, output the encoded string.

a

1 1
a: 0
0