题目描述

给定一个仅包含小写字母的字符串，去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

样例

输入："bcabc"
输出："abc"

输入："cbacdcbc"
输出："acdb"

算法

(贪心，栈) $O(n)$

1. 使用栈来贪心的构造最终的字符串，栈的更新规则如下。
2. 前提是当前字符没有在栈中出现。如果当前字符比栈顶字符的值小，且栈顶字符不是最后一次出现，则栈顶出栈。
3. 重复 2 直到栈空或栈顶不满足出栈条件。此时，将当前字符压入栈中，且标记当前字符出现过。
4. 最后将栈中元素从栈底到栈顶的顺序输出。

时间复杂度

• 预处理字符最后出现的位置为 $O(n)$。
• 每个元素最多进栈一次，出栈一次，故总时间复杂度为 $O(n)$。

空间复杂度

• 使用了栈来存储当前答案，但栈的大小最长不超过 26。
• 其他辅助和标记数组的长度都是 26，最后答案的长度也不超过 26。
• 所以可以认为空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<int> last(26, -1);
        vector<char> st;
        vector<bool> vis(26, false);
        int n = s.length();

        for (int i = 0; i < n; i++)
            last[s[i] - 'a'] = i;

        for (int i = 0; i < n; i++) {
            if (vis[s[i] - 'a'])
                continue;
            while (!st.empty() && st.back() > s[i]) {
                if (last[st.back() - 'a'] < i)
                    break;
                vis[st.back() - 'a'] = false;
                st.pop_back();
            }
            st.push_back(s[i]);
            vis[s[i] - 'a'] = true;
        }

        string ans;
        for (char c : st)
            ans += c;
        return ans;
    }
};