using System;
using System.Collections.Generic;
using System.Text;

namespace hafman
{
    public class HaffmanTree
    {
        public char C { get; private set; }
        public bool IsChar { get; private set; }
        public int Count { get; set; }
        public string Text { get; set; }

        public HaffmanTree LeftChild;
        public HaffmanTree RightChild;

        public HaffmanTree(char c, bool isChar, int count)
        {
            C = c;
            IsChar = isChar;
            Count = count;
        }
    }

    class Hafman
    {
        public HaffmanTree HaffmanTree;

        private string[] BuildTree(IEnumerable<char> s)
        {
            var charListIn      = new int[65536];
            var charListOut     = new string[65536];
            var listHaffmanTree = new List<HaffmanTree>();

            foreach (var t in s)
            {
                charListIn[t]++;
            }

            for (var i = 0; i < charListIn.Length; i++)
            {
                if (charListIn[i] > 0)
                    listHaffmanTree.Add(new HaffmanTree((char)i, true, charListIn[i]));
            }

            if (listHaffmanTree.Count <= 1)
            {
                if (listHaffmanTree.Count ==1)
                {
                    HaffmanTree = listHaffmanTree[0];
                    HaffmanTree.Text = "0";
                }
                return charListOut;
            }

            while (listHaffmanTree.Count > 1)
            {
                listHaffmanTree.Sort(new Comparison<HaffmanTree>((a, b) => a.Count - b.Count));
                listHaffmanTree.Add(Merge(listHaffmanTree[0], listHaffmanTree[1]));
                listHaffmanTree.RemoveAt(0);
                listHaffmanTree.RemoveAt(0);
            }

            HaffmanTree = listHaffmanTree[0];
            SetText(HaffmanTree, "");
            GetText(HaffmanTree, charListOut);
            return charListOut;
        }

        public string Encode(string s)
        {
            var temp = BuildTree(s);
            var sb = new StringBuilder();
            foreach (var a in s)
            {
                sb.Append(temp[a] + " ");
            }
            return sb.ToString();
        }

        private static void SetText(HaffmanTree ht, string s)
        {
            ht.Text = s;
            if(ht.LeftChild!=null)
            {
                SetText(ht.LeftChild,s+"0");
            }
            if (ht.RightChild != null)
            {
                SetText(ht.RightChild, s + "1");
            }
        }

        private static void GetText(HaffmanTree ht, IList<string> charListOut)
        {
            if(ht.IsChar)
            {
                charListOut[ht.C] = ht.Text;
            }
            if (ht.LeftChild != null)
            {
                GetText(ht.LeftChild, charListOut);
            }
            if (ht.RightChild != null)
            {
                GetText(ht.RightChild, charListOut);
            }
        }

        private static HaffmanTree Merge(HaffmanTree a,HaffmanTree b)
        {
            return new HaffmanTree('\0',false,a.Count+b.Count)
                       {
                           LeftChild  = a,
                           RightChild = b
                       };
        }
    }
}