题目内容

密码学家 Alice 获得了一段长度为 $n$ 的报文，由小写字母组成。她需要删除尽可能少的字符，使得剩余字符串中，字母的出现次数满足按字母表顺序非降：即对于任意小写字母 $x$ 和 $y$，如果 $x$ 在字母表中位于 $y$ 之前，则 $x$ 的出现次数不得超过 $y$ 的出现次数。在所有能达成这一条件的字符串中，Alice 希望选出字典序最小的作为最终结果。

字符串的长度 $n$ 不超过 $2 \times 10^5$，所有字符均为小写字母。保证输入字符串至少包含一个字母 'z'。

输入描述

第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)。 第二行包含一个长度为 $n$ 的字符串 $s$，由小写字母组成，且至少含有一个 'z'。

输出描述

输出一行，包含一个字符串，表示满足条件且字典序最小的结果。

样例1

输入

1
z

输出

z

说明

字符串由单个字符 'z' 组成，出现次数为 1，已经满足非降条件，不需要删除任何字符。

样例2

输入

3
abz

输出

z

说明

字符串中含 'a'、'b'、'z'，但缺少 'c' 到 'y'。根据规则，若保留 'a' 或 'b'，它们的出现次数必须不超过所有字母表顺序靠后的字母，而缺失的字母出现次数为 0，会导致无法满足非降要求。因此只能保留连续后缀 'z'，需要删除 2 个字符，得到 "z"。

样例3

输入

5
xyxzy

输出

xyz

说明

字符串仅由 'x'、'y'、'z' 组成，且字母连续到 'z'。原始频次为 x:2、y:1、z:1。

配额从右向左截顶：$c[\text{z}]=1$，$c[\text{y}]=\min(1,1)=1$，$c[\text{x}]=\min(2,1)=1$，即每个字母最多保留 1 个。

原串中选取索引 1 的 'x'、索引 2 的 'y'、索引 4 的 'z'，得到 "xyz"，频次均为 1，满足 $1 \le 1 \le 1$，且字典序最小。

样例4

输入

7
yyxzyyx

输出

xzy

说明

字母 'x'、'y'、'z' 连续出现。原始频次：x:2、y:4、z:1。配额截顶后 $c[\text{z}]=1$，$c[\text{y}]=\min(4,1)=1$，$c[\text{x}]=\min(2,1)=1$，每字母最多保留 1 个。

贪心过程：

• 第 1 个 'y' 入栈，栈为 ['y']；
• 第 2 个 'y' 跳过；
• 遇到 'x' 时，栈顶 'y' 大于 'x'，此时后面还剩 2 个 'y'，满足 $\text{remain}[\text{y}] \ge \text{need}[\text{y}]+1$，弹出 'y'，将 'x' 入栈，栈变为 ['x']；
• 'z' 入栈得 ['x','z']；
• 后续 'y' 因栈顶 'z' 无法弹出（剩余 'z' 不足），入栈得 ['x','z','y']；
• 其余字符跳过。

结果为 "xzy"，既满足频次要求，又比 "yxz" 等方案字典序更小。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写