解题思路

要得到 $s$ 的一个子序列：每个出现过的字母恰好一次，且字典序最小。用单调栈从左到右贪心。

先记下每个字母最后一次出现的下标。后面能不能再「用掉」某个字母，看这个下标。
从左到右扫。若当前字母已经在栈里，再放一次会重复，直接跳过。
若栈顶字母比当前字母大，并且栈顶字母在后面还会出现，就弹出栈顶。这样可以把更小的字母推到更前面，被弹出的字母以后还能再选。
栈顶不能弹（比当前小，或后面再也没有了）时，把当前字母入栈。
常见假解：每个字母只留第一次出现（样例 $1$ 会得到 $bca$ ）；只留最后一次出现（样例 $2$ 会得到 $adbc$ ）；当成可以任意重排，输出排序后的去重串（ $ba$ 会错成 $ab$ ）。

题目内容

给定一个仅由小写英文字母组成的字符串 $s$ 。

请删除字符串中的一些字符，使得最终字符串中的每个字母都只出现一次，并且原字符串中剩余字符的相对位置不能发生改变。

在所有满足条件的结果中，请输出字典序最小的字符串。

输入一行字符串 $s$ ，表示给定的字符串。

$1 \le |s| \le 10^4$

字符串 $s$ 仅由小写英文字母组成。

输出一个字符串，表示删除重复字母后得到的字典序最小结果。

要求结果中的每个字母只出现一次，并且不能改变剩余字符在原字符串中的相对位置。

输入

bcabc

输出

abc

说明

字符串 $s$ 中包含字母 $a$ 、 $b$ 、 $c$ 。

删除重复字母后，可以得到多个满足每个字母只出现一次的结果。

其中 $abc$ 的字典序最小，因此输出 $abc$ 。

输入

cbacdcbc

输出

acdb

说明

字符串 $s$ 中包含字母 $a$ 、 $b$ 、 $c$ 、 $d$ 。

在保证每个字母只出现一次，并且不改变剩余字符相对位置的情况下，字典序最小的结果为 $acdb$ 。

选择提交后点击「开始AI分析」