#P18020. Optimal Splitting
Optimal Splitting
Optimal Splitting
给定一个长度为 、仅含小写英文字母的字符串 。把 的每个字符恰好分配给两个子序列 中的一个,子序列中的字符保持它们在 中的先后顺序。允许某个子序列为空。
若 ,交换两者,使得 。在 末尾补上若干个字符 a,直到 。然后构造长度为 的字符串 ,其中
字符大小按照英文字母顺序比较。求所有分配方式中,字典序最小的 。
字典序规定:如果一个字符串是另一个字符串的真前缀,则较短者更小;否则比较第一个不同位置上的字符。
输入格式
第一行一个整数 。每组数据第一行一个整数 ,第二行一个长度为 的字符串 。
输出格式
每组数据输出一行,表示字典序最小的字符串 。
数据范围
,。 只含小写英文字母。所有测试用例的 之和不超过 。
样例 1
输入
3
1
a
2
za
5
ababa
输出
a
z
aba