← 返回题目列表

AtCoder · arc134_b

B. 保留或反向

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给定的是一个字符串 s 长度 N。 让 s_i 表示 i- 第一个字符 s.

Snuke 将变形 s 通过以下步骤。

  • 选择一个 偶数长度 (不一定连续)子序列 x=(x_1, x_2, \ldots, x_{2k}) of (1,2, \ldots, N) (k 可能是 0).
  • 交换 s_{x_1} 和 s_{x_{2k}}.
  • 交换 s_{x_2} 和 s_{x_{2k-1}}.
  • 交换 s_{x_3} 和 s_{x_{2k-2}}.
  • \vdots
  • 交换 s_{x_{k}} 和 s_{x_{k+1}}.

在字符串中 s 经过程序就可以找到字典序最小的一个。

字典顺序是什么?

简单来说,词典顺序就是单词在词典中列出的顺序。作为更正式的定义,这里是确定不同字符串之间的字典顺序的算法 S 和 T.

下面,让 S_i 表示 i- 第一个字符 S。另外,如果 S 按字典顺序小于 T,我们将该事实表示为 S \lt T;如果 S 按字典顺序大于 T,我们将该事实表示为 S \gt T.

  1. 让 L 是以下长度中较小的一个 S 和 T。对于每个 i=1,2,\dots,L,我们检查是否 S_i 和 T_i 是相同的。
  2. 如果有 i 这样 S_i \neq T_i,让 j 是最小的这样 i。然后,我们比较 S_j 和 T_j。如果 S_j 早于 T_j 按字母顺序排列,我们确定 S \lt T 然后退出;如果 S_j 晚于 T_j,我们确定 S \gt T 然后退出。
  3. 如果没有 i 这样 S_i \neq T_i,我们比较长度 S 和 T。如果 S 短于 T,我们确定 S \lt T 然后退出;如果 S 长于 T,我们确定 S \gt T 然后退出。

约束

  • 1 \leq N \leq 2 \times 10^5
  • s 是一个长度为的字符串 N 由小写英文字母组成。

输入

输入由标准输入按以下格式给出:

N
s

输出

打印字典顺序最小的可能字符串 s 在 Snuke 的程序之后。


示例输入 1

4
dcab

示例输出 1

acdb
  • 当 选择 x=(1,3),程序只是交换 s_{1} 和 s_{3}.
  • 的 s 程序后 acdb,按字典顺序排列的最小可能结果。

示例输入 2

2
ab

示例输出 2

ab
  • 当 选择 x=(), s 程序后 ab,按字典顺序排列的最小可能结果。
  • 请注意 x 的长度可能为 0.

示例输入 3

16
cabaaabbbabcbaba

示例输出 3

aaaaaaabbbbcbbbc

示例输入 4

17
snwfpfwipeusiwkzo

示例输出 4

effwpnwipsusiwkzo