1081. Smallest Subsequence of Distinct Characters

题目信息

题号:

1081

难度:

Medium

主题:

字符串、子序列、字典序最小化

原题:

LeetCode 1081

重点:

结果必须包含 s 中每种不同字符恰好一次,并保持所选字符的原始相对顺序;在所有合法子序列中字典序最小

题目重述

给定只包含小写英文字母的字符串 s。从中删除若干字符但不改变剩余字符的相对顺序,得到一个子序列。

要求结果包含 s 中出现过的每一种不同字符,并且每种字符恰好出现一次。在所有满足条件的子序列中,返回字典序最小的字符串。

1 <= s.length <= 1000,s 只包含小写英文字母。

自建示例

较小字符若出现过晚,不一定能移到最前:

输入:s = "bdabac"
输出:"bdac"
解释:结果需要包含 a、b、c、d 各一次。由于 d 只在下标 1 出现,要保留 d 就必须先选择前面的 b;在此约束下 bdac 是字典序最小的合法子序列。

字符串只有一种字符:

输入:s = "z"
输出:"z"
解释:唯一字符必须恰好保留一次,因此结果就是 z。