#P18302. Anthem
Anthem
Anthem
几个世纪以来,吹笛矮人每天早晨都会用他巨大的管风琴演奏矮人国歌。但现在他必须搬到一个空间有限的新洞穴,原来的管风琴放不下了。
国歌是一个音符序列,每个音符用从 a 到 z 的小写英文字母表示。管风琴的每根音管都只能演奏一个指定的音符。吹笛矮人想制作一架音管数量尽可能少、又能够演奏整首国歌的小型管风琴。
所有音管排成一行。演奏时,吹笛矮人可以从任意一根音管开始。吹奏当前音管、发出对应的音符后,他可以留在原处,也可以移动到紧邻的左侧或右侧音管,再吹奏下一个音符。他可以在任意位置结束演奏。
请构造能够演奏给定国歌、且音管数量最少的管风琴。
输入格式
第一行包含整数 ,表示国歌的音符数。
第二行包含一个长度为 、仅由小写英文字母组成的字符串,表示国歌。
输入仅有一组数据。
输出格式
第一行输出整数 ,表示所需音管的最少数量。
第二行输出一个长度为 的小写英文字母字符串,按从左到右的顺序描述每根音管所演奏的音符。
如果存在多种最短的管风琴,输出任意一种即可。
数据范围
。
样例
14
ecerrcwrwcwror
7
cercwro