1081. Smallest Subsequence of Distinct Characters

Link: [https://leetcode.com/problems/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.

---

題目翻譯:

X

程式思路:

X

class Solution {
public:
    string smallestSubsequence(string s) {
        vector <int> seen (26,false);
        vector <int> freq (26,0);
        stack <char> stk;
        for (auto c : s) {
            freq[c - 'a']++;
        }

        for (int i = 0; i < s.length(); i++) {
            char ch = s[i];

            freq[ch - 'a']--;
            if (seen[ch - 'a'])
                continue;

            while (!stk.empty() && stk.top() > ch && freq[stk.top() - 'a'] > 0) {
                seen[stk.top() - 'a'] = false;
                stk.pop();
            }

            stk.push(ch);
            seen[ch - 'a'] = true;
        }

        string res;
        while (!stk.empty()) {
            res += stk.top();
            stk.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};