递归构建哈夫曼分形树

Python Hard recursion

任务 «递归构建哈夫曼分形树»

给定一个由拉丁字母（小写）组成的字符串。需要构建一棵哈夫曼分形树：计算每个字符的频率，然后递归构建一棵树，其中每个节点包含左子树和右子树的频率之和，叶子节点包含字符。在递归的每一步，需要将字符列表分成两部分，使得左部分的频率之和尽可能接近右部分的频率之和（贪心算法）。返回一个表示树的字符串，采用前缀表示法：对于节点——'F{总和}'，对于叶子——'L{字符}'。必须使用递归。

输入格式

一行由小写拉丁字母组成的字符串（长度从1到100）。

输出格式

字符串——不带空格的树的前缀表示法。

示例

示例 1

输入

1
42

输出

L1

示例 2

输入

nil nil nil

输出

F11F6LnLiF5LlL 

示例 3

输入

abc

输出

F3LaF2LbLc

示例 4

输入

0 1 2

输出

F5F3L0L F2L1L2

main.py