题解

题面描述

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

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

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

题目内容

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

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

• 选择两个不同的位置$i$和$j$(满足$i≠j$)，要求$s[i]≠'a' 且 s[j] ≠'z'$;
• 将$s[i]$ 替换为其前一个字母(即字母表中前一位)，同时将$s[j]$替换为其后一个字母(即字母表中后一位).

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

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

输入描述

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

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

输出描述

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

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

样例1

输入

2
bb

输出

ac 

说明

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

样例2

输入

3
aaa

输出

aaa

说明

• 字符串中所有字符均为$’a’$，不存在满足条件的操作，因此输出原字符串。