问题 H: RS哥哥的字符串

问题 H: RS哥哥的字符串

时间限制: 1 Sec  内存限制: 128 MB
提交: 181  解决: 32
[状态] [讨论版] [提交] [命题人:]
题目描述
初始有一个仅包含小写字母的字符串s,每次操作可以交换s任意两个位置上的字符,操作可以进行任意次。
操作完成后,rs哥哥想将调整后的字符串s'切割成m(m>=2)段,每段分别为t1,t2,...,tm,同时需要满足以下两个条件:
t1+t2+...+tm = s';
t1 = t2 = .... = tm;
满足条件的划分方式可能会有很多种,rs哥哥想知道在最大化m的前提下t1的字典序最小的划分方式,你能告诉rs哥哥吗?
输入
输入一行包含仅由小写字符组成的字符串s(1<=|s|<=106)。
输出
输出第一行包含一个整数m。代表在采用如题面所述的划分方式时,s'能被分成m段;如果不存在满足条件的划分方式,则输出0.
输出第二行包含一个字符串t1。表示在采用如题面所述的划分方式时的t1;如果不存在满足条件的划分方式,则不需要输出第二行。
样例输入 Copy
cbaabc

abcdefg
样例输出 Copy
2
abc

0
提示
本题单实例,样例输入、样例输出中是两组数据。
case1:将s重排为abcabc,切成两段,t1 = t2 = abc 。
case2:不存在满足条件的切割方式。