[LeetCode] 1081. Smallest Subsequence of Distinct Characters

[grandyang]

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 同步地址:

#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 题目讲解汇总(持续更新中...)