The goal of Huffman codes is to implement a variable length encoding scheme that allows us to do lossless compression by just changing the bits that we used to represent each symbol.

The problem of Huffman codes is just a specific case of the problem where we want to find the minimum of pairwise combinations of a sequence of values.

The genius of a Huffman code is the conversion of the problem of compression into a tree problem that comes down to pairwise combinations of nodes.

We represent an encoding of a word as a sequence of bits, build up by traversing downwards through a tree. To make it possible to identify each character separately in a string, we ensure that a character encoding ends when a leaf is reached. This is equivalent to ensuring that there are no overlapping prefixes.

Proof of optimality

Like all Greedy algorithms, it is important to prove the optimality of the solution obtained by leveraging the optimal substructure of the problem. In this case, we use induction followed by an exchange argument to prove that the solution is optimal.

Note: We have reformulated the problem as a tree problem that makes it clear that we need can use induction to approach the proof.