Описание задачи

По данной непустой строке ss длины не более 10^4, состоящей из строчных букв латинского алфавита, постройте оптимальный беспрефиксный код. В первой строке выведите количество различных букв k, встречающихся в строке, и размер получившейся закодированной строки. В следующих k строках запишите коды букв в формате “letter: code”. В последней строке выведите закодированную строку.

Надежный шаг

Чтобы решить данную задачу нужно посчитать частоту вхождения каждого символа в строку а после построить дерево где листья - символы имеющие свой вес (частота вхождения) а узлы - сумма всех нижестоящих узлов/листьев.

Это позволит потом вычислить оптимальные коды, так как при правильном построении данного бинарного дерева наиболее часто встречающиеся символы будут расположены ближе к корню а значит займут меньшее место в итоговом коде.

Надежным шагом в данной задаче является выбор двух узлов (в начале там только символы) с наименьшими вхождениями и помещением их в один узел (так, чтобы они стали братьями).

Huffman coding

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.stream.Collectors;

/**
 * Main
 *
 * @author Vladislav Sidlyarevich <vlsidlyarevich@gmail.com>
 * Created on 4/28/21.
 */
public class Main {

    public static void main(String[] args) {
        Main main = new Main();
        main.run();
    }

    public void run() {
        Scanner scanner = new Scanner(System.in).useDelimiter("\n");
        String input = scanner.nextLine();

        //Calculate frequency of chars in string
        Map<Character, Integer> frequency = calculateFrequency(input);

        PriorityQueue<Node> nodes = new PriorityQueue<>();

        //Add initial nodes
        for (Map.Entry<Character, Integer> entry : frequency.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }

        //Build binary tree
        while (nodes.size() != 1) {
            Node firstNode = nodes.poll();
            Node secondNode = nodes.poll();

            Node newNode = new Node(firstNode, secondNode, firstNode.weight + secondNode.weight);
            nodes.remove(firstNode);
            nodes.remove(secondNode);
            nodes.add(newNode);
        }

        Map<Character, String> codes = frequency.keySet().stream()
                .collect(Collectors.toMap(v -> v, v -> ""));

        //Traverse the tree and fulfill codes map
        fillCodes(nodes.peek(), codes, "");
        //Encode the input
        String encodedInput = encode(codes, input);

        printResults(codes, encodedInput);
    }

    private void printResults(final Map<Character, String> codes, final String encodedInput) {
        System.out.println(codes.keySet().size() + " " + encodedInput.length());
        codes.forEach((ch, code) -> System.out.println(ch + ": " + code));
        System.out.println(encodedInput);
    }

    private String encode(final Map<Character, String> codes, final String input) {
        StringBuilder result = new StringBuilder();
        for (char ch : input.toCharArray()) {
            result.append(codes.get(ch));
        }

        return result.toString();
    }

    private Map<Character, Integer> calculateFrequency(final String input) {
        Map<Character, Integer> result = new HashMap<>();
        for (char c : input.toCharArray()) {
            result.merge(c, 1, Integer::sum);
        }

        return result;
    }

    private void fillCodes(Node root, Map<Character, String> codes, String code) {
        if (root.isLeaf()) {
            //Put code into codes dictionary and handle case when single node
            codes.put(root.character, code.isEmpty() ? "0" : code);
            return;
        }

        fillCodes(root.leftNode, codes, code + "0");
        fillCodes(root.rightNode, codes, code + "1");
    }

    static class Node implements Comparable<Node> {

        private Node leftNode;
        private Node rightNode;

        private Character character;

        private Integer weight;

        public Node(final Character character, final Integer weight) {
            this.character = character;
            this.weight = weight;
        }

        public Node(final Node leftNode, final Node rightNode, final Integer weight) {
            this.leftNode = leftNode;
            this.rightNode = rightNode;
            this.weight = weight;
        }

        boolean isLeaf() {
            return this.leftNode == null && this.rightNode == null && this.character != null;
        }

        @Override
        public int compareTo(final Node o) {
            if (o.weight.equals(weight)) return 0;
            return o.weight > weight ? -1 : 1;
        }
    }
}