316 Remove Duplicate Letters 去除重復字母

Description:
Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Note:
This question is the same as 1081

Example:

Example 1:

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

Example 2:

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

Constraints:

1 <= s.length <= 10^4
s consists of lowercase English letters.

題目描述:
給你一個字符串 s 槐脏，請你去除字符串中重復的字母半醉，使得每個字母只出現(xiàn)一次队丝。需保證 返回結(jié)果的字典序最薪榻佟（要求不能打亂其他字符的相對位置）侥蒙。

注意：
該題與 1081 相同

示例 :

示例 1：

輸入：s = "bcabc"
輸出："abc"

示例 2：

輸入：s = "cbacdcbc"
輸出："acdb"

提示：

1 <= s.length <= 10^4
s 由小寫英文字母組成

思路:

單調(diào)棧
先統(tǒng)計字符串中的字符的個數(shù)
遍歷字符串, 減去對應的字符
訪問過的字符就跳過
如果棧中的元素比遍歷的字符要大, 嘗試彈出
如果之后沒有該元素, 就不彈出, 否則全部彈出直到遍歷元素為最小元素
時間復雜度O(n), 空間復雜度O(n)

代碼:
C++:

class Solution 
{
public:
    string removeDuplicateLetters(string s) 
    {
        vector<int> count(128);
        vector<bool> visited(128, false);
        for (auto &c : s) ++count[c];
        string result = "0";
        for (auto &c : s)
        {
            --count[c];
            if (visited[c]) continue;
            while (c < result.back() and count[result.back()])
            {
                visited[result.back()] = false;
                result.pop_back();
            }
            result += c;
            visited[c] = true;
        }
        return result.substr(1);
    }
};

Java:

class Solution {
    public String removeDuplicateLetters(String s) {
        Stack<Character> stack = new Stack<>();
        boolean visited[] = new boolean[128];
        int count[] = new int[128];
        for (char c : s.toCharArray()) ++count[c];
        for (char c : s.toCharArray()) {
            --count[c];
            if (visited[c]) continue;
            while (!stack.isEmpty() && stack.peek() > c) {
                if (count[stack.peek()] == 0) break;
                visited[stack.pop()] = false;
            }
            stack.push(c);
            visited[c] = true;
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) sb.append(stack.pop());
        return sb.reverse().toString();
    }
}

Python:

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        for a in sorted(set(s)):
            temp = s[s.index(a):]
            if len(set(temp)) == len(set(s)):
                return a + self.removeDuplicateLetters(temp.replace(a, ""))
        return ""