P3724.第2题-被污染的符文

1000ms

Difficulty: 3

所属公司 : 携程

算法与标签>栈

题目内容

游游手上有一个被污染的符文，这个符文上刻着一个长度为 $n$ 的字符串 $s$ (仅由大小写英文字母构成，下标从 $1$ 开始)。为了清除污染，Tk 将依次执行如下两步操作:

先从左到右(按下标从小到大)依次处理每个位置 $i$ 上的字符 $s_i$ ；
- 若 $s_i$ 为小写字母，则将 $s_i$ 替换为其在字母表中的循环前驱；特别地， $'a’$ 的循环前驱为 $'z’$ ;
- 若 $s_i$ 为大写字母，则将 $s_i$ ，替换为其在字母表中的循环后继；特别地， $'Z'$ 的循环后继为 $'A'$ )。
在完成上述所有替换后，再从右到左(按下标从大到小)依次处理每个位置 $i$ 上的字符 $s_i$ :
- 若 $s_i$ ，不是当前最新字符串的最后一个字符，且在当前最新字符串中它右侧紧邻的那个字符与 $s_i$ 为同字母异大小写，则删除 $s_i$ ;
- 每次删除后，剩余字符按原有先后顺序连接，继续上述判断，直至处理完毕。

请输出游游完成全部操作后得到的字符串。

【名词解释】

循环前驱：对小写字母而言，若为 $'a’$ 则其循环前驱为 $'z’$ ，否则为其在字母表中的上一个小写字母。

循环后继：对大写字母而言，若为 $'Z'$ 则其循环后继为 $'A’$ ，否则为其在字母表中的下一个大写字母。

同字母异大小写：两个字符在忽略大小写后相同，且一个为小写另一个为大写，例如 $'a’$ 与 $'A'$ 。

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

第二行输入一个长度为 $n$ 的字符串 $s$ ，由大小写英文字母构成。

输出一个字符串，表示最终结果。

输入

2
bZ

输出

输入

3
bZb

输出

aa

说明

初始 $s ="bZb"$ 。

第二步从右往左处理：右端 $'a’$ 保留；其左侧的 $'A'$ 与右邻 $'a’$ 为同字母异大小写，被删除；再看最左侧的 $'a’$ ，其右邻为 $'a’$ (大小写相同)，因此保留，最终为 $"aa"$ 。

输入

2
aZ

输出

zA

输入

预期输出（选填）