---
# System prepended metadata

title: 316. Remove Duplicate Letters
tags: [Leetcode, greedy, stack, medium, python, c++]

---

###### 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:
``` 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++:
``` cpp=
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;
    }
};
```