###### tags: `Leetcode` `medium` `greedy` `stack` `python` `c++`

# 316. Remove Duplicate Letters

## [題目連結:] https://leetcode.com/problems/remove-duplicate-letters/

## 題目:
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.

**Example 1:**

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

**Example 2:**

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

## 解題想法:
* 此題為，刪除掉重複的字符，並使其字典序為最小
* ex: abc< bca

* 想法:
* 何時能刪除掉此字符?
* case1: **刪掉此字符能此字典序變更小**
* case2: **該字符之後還會出現**
* 流程:
* Step1: 初始
* stack=[] :存字符
* seen=set() :紀錄已經看過
* last={} :紀錄每個字符最後一次出現的位置
* Step2:
* 先遍歷一次字串，last紀錄各自符位置
* Step3:
* 再遍歷一次字串，對於沒出現過的字符才需要繼續進行:
* **判斷stack中的字符是否需要被pop**
* 須滿足case1、case2條件才能pop
* pop出去能使序列變小ex: abc < acb
* **被pop出去的val不是最後一次出現**
* 若能pop，須將該刪除的字符於seen中一併刪除
* 將當前字符於seen中紀錄為true
* stack.append(當前字符)
* Step4:
* 合併stack為字串

## Python:

class Solution(object):
    def removeDuplicateLetters(self, s):
        """
        :type s: str
        :rtype: str
        """
        stack=[]
        seen=set() #紀錄已看過
        last={} #last紀錄每個char最後一次出現位置
        for pos,val in enumerate(s):
            last[val]=pos
        for pos,val in enumerate(s):
            #沒出現過才要進去考慮
            if val not in seen: #用set找 O(1)
                #判斷stack裡面的需不需要pop出去
                #須滿足兩個條件:
                #1. pop出去能使序列變小ex abc < acb
                #2. 被pop的val不是最後一次出現
                while stack and val<stack[-1] and pos<last[stack[-1]]:
                    #set刪除用remove
                    seen.remove(stack.pop())
                seen.add(val)
                stack.append(val)
        return "".join(stack)

result = Solution()
s = "cbacdcbc"
print(result.removeDuplicateLetters(s))

## C++:

class Solution {
public:
    string removeDuplicateLetters(string s) {
        stack<char> res;
        unordered_set<char> seen; // insert erase
        unordered_map<char,int> last; //record location
        for (int i=0; i<s.size(); i++) last[s[i]]=i;
        // check every char
        for (int i=0; i<s.size(); i++){
            if (seen.find(s[i])==seen.end()){
                while (!res.empty() && s[i]<res.top() && i<last[res.top()]){
                    seen.erase(res.top());
                    res.pop();
                }
                seen.insert(s[i]);
                res.push(s[i]);
            }
        }
        // convert stack to string
        string ans;
        while (!res.empty()){
            ans.push_back(res.top());
            res.pop();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};