分数: 800 点
问题陈述
给定的是一个字符串 S 组成 a 和 b。按字典顺序查找 最大 字符串,可通过以下操作获得 S 零次或多次:
- 选择两个字符 S 是相同的字母。反转它们之间的字符串并删除所选的两个字符。换句话说:让 s_i 表示 i- 第一个字符 S。选择 i < j 这样 s_i = s_j 并替换 S 与 s_1\dots s_{i-1}s_{j-1}\dots s_{i+1}s_{j+1}\dots s_{|S|}.
在这个问题中,给你 T 测试用例。的 i第一个测试用例表示为 S_i 并请您解决上述问题 S = S_i.
约束
- 1 \leq T \leq 2\times 10^5
- 1 \leq |S_i|\quad (i=1,\dots, T)
- 1 \leq |S_1| + \dots + |S_T| \leq 2\times 10^5
- S_i 包括
a和b.
输入
输入由标准输入按以下格式给出:
T S_1 \vdots S_T
输出
打印 T 行。的 i- 第行应包含按字典顺序排列的最大字符串,该字符串可通过将操作应用于 S_i 零次或多次。
示例输入 1
20 abbaa babbb aabbabaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb bbabaaaaabbaababaaabbabbbbbaaaaa babbbaaaabaababbbabaabaaaaababaa bbaababababbbaaabaabababaabbabab abaabbabaabaaaaabaaaabbaabaaaaab aabababbabbabbabbaaaabbabbbabaab aabababbabbbbaaaabbaaaaabbaaaabb abbbbaabaaabababaaaababababbaabb aaaaaaaaaaaaaaaaaaaaaaabbbbbbbbb aaaaaaaaaabbbbbbbbbbbbbbbbbbbbbb abababaaababaaabbbbbaaaaaaabbbbb aabbaaaaababaabbbbbbbbbaabaaabbb babababbababbbababbbbbababbbabbb bbbbababbababbbabababbabbabbbbbb aaaaaaaaaaaaaaaaababababbbabbbbb aabababbabbabababababababbbbabbb
示例输出 1
bba bba bbba aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb bbbbbbbbbbbbbbaaaaaaaa bbbbbbbbbbbbbaaaaaaa bbbbbbbbbbbbbbbb bbbbbbbbbb bbbbbbbbbbbbbbbbab bbbbbbbbbbbbbb bbbbbbbbbbbbbabb abbbbbbbbb bbbbbbbbbbbbbbbbbbbbbb bbbbbbbbbbbbbaaaaaaaaa bbbbbbbbbbbbbbbaaaaa bbbbbbbbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbbbbbbba bbbbbbbbbaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbba
- 在 1-st 测试用例,我们可以执行以下操作 1-st 和 4要制作的第个字符 S
bba. - 在 2-nd测试用例,我们可以执行以下操作 1-st 和 5要制作的第个字符 S
bba. - 在 3-rd 测试用例,我们可以执行以下操作 1-st 和 2-要制作的第一个字符 S
bbabaa,然后为 3-rd 和 5要制作的第个字符 Sbbba.