题解

给定一个长度为 $n$ 的字符串 $s$ ，其中 $s$ 由小写字母构成。我们可以进行任意次如下操作：

选择两个不同的位置 $i$ 和 $j$ （满足 $i \neq j$ ），要求 $s[i] \neq \texttt{’a’}$ 且 $s[j] \neq \texttt{’z’}$ ；
将 $s[i]$ 替换为其前一个字母（即字母表中前一位），同时将 $s[j]$ 替换为其后一个字母（即字母表中后一位）。

P2881.第1题-TK的字符串调整

1000ms

Difficulty: 3

所属公司 : 饿了么

算法与标签>贪心算法

$Tk$ 有一个长度为n的字符串 $s$ ，其中 $s$ 由小写字母构成。

你可以进行任意次如下操作:

在所有可能的合法操作中，选择得到字典顺序最小的字符串作为答案。若不存在合法的操作，则输出原字符串。

从字符串的第一个字符开始逐个比较，直至发现第一个不同的位置，比较这个位置字符的字母表顺序，字母序较小的字符串字典序也较小。

输入第一行包含一个整数 $n(1≦n≦2×10^5)$ ，表示字符串的长度。

输入第二行包含一个字符串 $s$ ，该字符串仅由小写字母构成

输出经过任意次合法操作后能得到的字典顺序最小的字符串。

若不存在合法的操作，则输出原字符串。

输入

2
bb

输出

ac

说明

对样例选择 $i= 1$ (将 $s[1]$ 从 $’b’$ 变为 $'a'$ ) 和 $j=2$ (将 $s[2]$ 从 $'b'$ 变为 $'c'$ )，结果得到字符串" $ac$ "，这是所有操作中字典顺序最小的字符串。

输入

3
aaa

输出

aaa

说明

输入

预期输出（选填）