import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.ArrayList;

class Huffman_wartosc
{

    int ile;
    char znak;
    boolean czy_z;
    int zsum;

    Huffman_wartosc lewy;
    Huffman_wartosc prawy;

    public Huffman_wartosc()
    {
        ile = 0;
        znak = '~';
        czy_z = false;
        zsum = 0;
        lewy = null;
        prawy = null;
    }

    public Huffman_wartosc(int a, char z, boolean czy, int sum)
    {
        ile = a;
        znak = z;
        czy_z = czy;
        zsum = sum;
        lewy = null;
        prawy = null;
    }

    public Huffman_wartosc(int a, char z, boolean czy, int sum, Huffman_wartosc l, Huffman_wartosc p)
    {
        ile = a;
        znak = z;
        czy_z = czy;
        zsum = sum;
        lewy = l;
        prawy = p;
    }


}

class wynik
{
    char z;
    int ilez;
    String kod;

    public wynik(int a, char b, String c)
    {
        z = b;
        ilez = a;
        kod = c;
    }
}



public class huffman {

    public static int extract_min(ArrayList<Huffman_wartosc> tabela)
    {
        int pozycja_min = 0;
        int min = 0;
        if(tabela.get(0).czy_z){ min=tabela.get(0).zsum;}
        else{min=tabela.get(0).ile;}

        for(int x=0; x<tabela.size(); x++)
        {


            if(tabela.get(x).czy_z)
            {
                if(tabela.get(x).zsum<min) {min = tabela.get(x).zsum; pozycja_min = x;}
            }
            else
            {
                if(tabela.get(x).ile<min) {min = tabela.get(x).ile; pozycja_min = x;}
            }
        }


        return pozycja_min;
    }

    public static void odczytaj_wynik(Huffman_wartosc ojciec, String kod)
    {
        if (ojciec.lewy == null && ojciec.prawy == null && !ojciec.czy_z)
        {
            System.out.println(ojciec.znak+"--"+ojciec.ile+"--"+ kod);
        }

        if (ojciec.lewy != null) {odczytaj_wynik(ojciec.lewy, kod + '0');}
        if (ojciec.prawy != null) {odczytaj_wynik(ojciec.prawy, kod + '1');}


    }



    public static void main(String[] args) throws FileNotFoundException{

        Huffman_wartosc tablica[] = new Huffman_wartosc[255];

        File plik = new File("tekst2");
        Scanner odczyt = new Scanner(plik);

        String zdanie = odczyt.nextLine();
        //System.out.println(zdanie.length());
        int[] ile = new int[zdanie.length()];
        //Konwertuje zdanie na to by skladalo sie z poszczegolnych znakow
        //gdzie kazdy bedzie rozpatrywany osobno
        char zdanie_z_charow[] = zdanie.toCharArray();



        for(int i = 0; i <zdanie.length(); i++) {
            ile[i] = 1;
            for(int j = i+1; j <zdanie.length(); j++) {
                if(zdanie_z_charow[i] == zdanie_z_charow[j]) {
                    ile[i]++;

                    //Ustawiamy na pozycje j-ta znak "~" ktory liczymy ze nie wystepuje
                    //w naszym zdaniu aby sie naliczal kilkuktrotnie a tylko 1 raz
                    zdanie_z_charow[j] = '~';
                }
            }
        }


        //Zadeklarowanie nowych tablic w celu przedstawienia
        // danych w klarowniejszy sposób

        char znak[] = new char[255];
        int ileznak[] = new int[255];
        int wypelniacz = 0;

        for(int i = 0; i <ile.length; i++)
        {
            if(zdanie_z_charow[i] != ' ' && zdanie_z_charow[i] != '~')
            {
                znak[wypelniacz] = zdanie_z_charow[i];
                ileznak[wypelniacz] = ile[i];
                wypelniacz++;
                //System.out.println(zdanie_z_charow[i] + "-" + ile[i]);
            }

        }

        System.out.println("Znaki i pod nimi ich liczba wystapien");
        for(int i=0; i<wypelniacz; i++)
        {
            System.out.print(""+znak[i]+"   ");
        }
        System.out.print("\n");
        for(int i=0; i<wypelniacz; i++)
        {
            System.out.print(""+ileznak[i]+"   ");
        }

        //Sortowanie tablicy wg ilosci znaków
        // aby pozniej bylo latwiej extractowac minimum

        for (int i=1; i<wypelniacz; i++)
        {
            int klucz = ileznak[i];
            char znakklucza = znak[i];
            int j = i - 1;

            while (j >= 0 && ileznak[j] > klucz)
            {
                ileznak[j+1] = ileznak[j];
                znak[j+1] = znak[j];
                j = j - 1;
            }
            ileznak[j+1] = klucz;
            znak[j+1] = znakklucza;
        }


        System.out.println("\n-------------------------------------------------------------------------------------------------------------------------------------------------------");
        System.out.println("Posortowane znaki i liczba ich wystapien po liczbie znakow");
        for(int i=0; i<wypelniacz; i++)
        {
            System.out.print(""+znak[i]+"   ");
        }
        System.out.print("\n");
        for(int i=0; i<wypelniacz; i++)
        {
            System.out.print(""+ileznak[i]+"   ");
        }
        System.out.println("\n-------------------------------------------------------------------------------------------------------------------------------------------------------");


        // Na nowo moze troche naokolo robione
        // ale deklaracja zmiennych w postaci tablicy Huffman_wartosci
        // ktore zawieraja znak, ileznak, i jesli to wezel typu z to sume wystapien jego synow
        // oraz moze zawierac lewego jak i prawego syna

        ArrayList<Huffman_wartosc> zbior = new ArrayList<Huffman_wartosc>();

//        Huffman_wartosc nowa = new Huffman_wartosc(11,'z',false,21);
//        System.out.print(""+nowa.ile+"  "+nowa.znak+"  "+nowa.czy_z+"  "+nowa.zsum);


        for(int i=0; i<wypelniacz; i++)
        {
            zbior.add( new Huffman_wartosc(ileznak[i],znak[i],false,0));
        }

//        System.out.println(extract_min(zbior));


        Huffman_wartosc a;
        Huffman_wartosc b;
        Huffman_wartosc z;
        int najmniejsza = 1;
        int korzen = 0;
        int sumaznakow = 0;

        for (int i=0; i<zbior.size(); i++)
        {
            korzen = korzen + zbior.get(i).ile;
        }

        System.out.println(korzen);

        while(korzen > sumaznakow )
        {
            najmniejsza = extract_min(zbior);
            a = zbior.get(najmniejsza);
            zbior.remove(najmniejsza);

            najmniejsza = extract_min(zbior);
            b = zbior.get(najmniejsza);
            zbior.remove(najmniejsza);

            if(b.czy_z && a.czy_z)
            {
                sumaznakow = a.zsum + b.zsum;
            }
            else if(b.czy_z)
            {
                sumaznakow = a.ile+b.zsum;
            }
            else if (a.czy_z)
            {
                sumaznakow = a.zsum + b.ile;
            }
            else
            {
                sumaznakow = a.ile+b.ile;
            }

            zbior.add( new Huffman_wartosc(0,' ',true,sumaznakow,a,b));

        }

       //ArrayList<wynik> tabela_wynikow = new ArrayList<wynik>();

        odczytaj_wynik(zbior.get(0),"");


//        for (int i=0; i<zbior.size(); i++)
//        {
//          System.out.print(""+zbior.get(i).ile+"  "+zbior.get(i).znak+"  "+zbior.get(i).czy_z+"  "+zbior.get(i).zsum+"\n");
//        }

    }


}