Задача «Рекурсивное построение фрактального дерева Хаффмана»

Дана строка из символов латинского алфавита (строчные буквы). Необходимо построить фрактальное дерево Хаффмана: для каждого символа вычислить его частоту, затем рекурсивно построить дерево, где каждый узел содержит сумму частот левого и правого поддеревьев, а листья содержат символы. На каждом шаге рекурсии нужно разделить список символов на две части так, чтобы сумма частот в левой части была максимально близка к сумме частот в правой части (жадный алгоритм). Вернуть строку, представляющую дерево в виде префиксной записи: для узла — 'F{сумма}', для листа — 'L{символ}'. Рекурсия обязательна.

Пример 1

Пример 2

Пример 3

Пример 4