Recursive construction of the Huffman fractal tree

Python Hard recursion

Task «Recursive construction of the Huffman fractal tree»

Given a string of Latin alphabet characters (lowercase letters). It is necessary to build a fractal Huffman tree: for each character, calculate its frequency, then recursively build a tree where each node contains the sum of the frequencies of the left and right subtrees, and the leaves contain characters. At each recursion step, the list of characters must be split into two parts so that the sum of frequencies in the left part is as close as possible to the sum of frequencies in the right part (greedy algorithm). Return a string representing the tree in prefix notation: for a node — 'F{sum}', for a leaf — 'L{character}'. Recursion is mandatory.

Input Format

One string consisting of lowercase Latin letters (length from 1 to 100).

Output Format

A string is a prefix notation of a tree without spaces.

Examples

Example 1

INPUT

1
42

OUTPUT

L1

Example 2

INPUT

nil nil nil

OUTPUT

F11F6LnLiF5LlL 

Example 3

INPUT

abc

OUTPUT

F3LaF2LbLc

Example 4

INPUT

0 1 2

OUTPUT

F5F3L0L F2L1L2

main.py