OJ现已增加邮箱找回密码功能，还没有绑定邮箱的同学们请抓紧时间，以免密码丢失无法找回


问题 G: 哈夫曼压缩

问题 G: 哈夫曼压缩

时间限制: 1 Sec  内存限制: 128 MB
提交: 1329  解决: 945
[提交] [状态] [讨论版] [命题人:]

题目描述

相信大家都对哈夫曼编码有所了解，通常利用哈夫曼编码来压缩数据。现在给你一个字符串，你需要统计其中字符出现的次数然后以出现次数为权值构建一棵哈夫曼树，例如字符串为ABBCCC，其中一种可能的编码是A = 00，B = 01，C = 1，那么这个字符串所对应的哈夫曼编码就是000101111，你的任务是求出字符串最终形成的哈夫曼编码的长度。

输入

一行由大写字母组成的字符串，且字符串长度不超过10000，该字符串最少包含一种字符。

输出

字符串的哈夫曼编码长度。

样例输入 Copy 

ABBCCC

样例输出 Copy 

9
[提交][状态]