1081. Smallest Subsequence of Distinct Characters

Return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.

Note: This question is the same as 316: https://leetcode.com/problems/remove-duplicate-letters/

Example 1:

Input: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

Constraints:

  • 1 <= s.length <= 1000
  • s consists of lowercase English letters.

这道题跟之前那道 Remove Duplicate Letters 一模一样,这已经不是第一次遇到这种情况了,博主就纳闷了怎么 LeetCode 就没有个查重系统呢,强行让我们复习以前做过的题目吗。这道题让找出字母顺序最小的一个子序列,使得所有的不同的字母只出现一次,之前那道题说的是去掉重复的字母使得每个字母只出现一次,且剩下的是字母顺序最小的一个。其实二者说的都是一个东西,这道题实际上需要用单调栈的思路来做,首先需要统计每个字母出现的次数,这里可以使用一个大小为 128 的数组 cnt 来表示,还需要一个数组 visited 来记录某个字母是否出现过。先遍历一遍字符串,统计每个字母出现的次数到 cnt 中。再遍历一遍给定的字符串,对于遍历到的字母,在 cnt 数组中减去一个,然后看该字母是否已经在 visited 数组中出现过,是的话直接跳过。否则需要进行一个 while 循环,这里的操作实际上是为了确保得到的结果是字母顺序最小的,若当前字母小于结果 res 中的最后一个字母,且该最后的字母在 cnt 中还存在,说明之后还会遇到这个字母,则可以在 res 中先去掉这个字母,以保证字母顺序最小,并且 visited 数组中标记为0,表示未访问。这里是尽可能的将 res 打造成单调递增的,但如果后面没有这个字母了,就不能移除,所以说并不能保证一定是单调递增的,但可以保证得到的结果是字母顺序最小的。while 循环退出后,将该字母加到结果 res 后,并且 visited 标记为1。这里还有个小 trick,结果 res 在初始化给个0,这样就不用判空了,而且0是小于所有字母的,不会影响这个逻辑,最后返回的时候去掉首位0就行了,参见代码如下:

class Solution {
public:
    string smallestSubsequence(string s) {
        string res = "0";
        vector<int> cnt(128), visited(128);
        for (char c : s) ++cnt[c];
        for (char c : s) {
            --cnt[c];
            if (visited[c]) continue;
            while (c < res.back() && cnt[res.back()]) {
                visited[res.back()] = 0;
                res.pop_back();
            }
            res += c;
            visited[c] = 1;
        }
        return res.substr(1);
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1081

类似题目:

Remove Duplicate Letters

参考资料:

https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/discuss/308194/C%2B%2B-O(n)-identical-to-316

https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/discuss/308210/JavaC%2B%2BPython-Stack-Solution-O(N)

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation