# 316. Remove Duplicate Letters 去除重复字母

@TOC

## # 题目描述

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example 1:

``````Input: "bcabc"
Output: "abc"
``````

Example 2:

``````Input: "cbacdcbc"
Output: "acdb"
``````

## # 解题方法

1. 如果当前字符c已经在栈里面出现，那么跳过。
2. 如果当前字符c在栈里面，那么：
1. 如果当前字符c小于栈顶，并且栈顶元素有剩余（后面还能再添加进来），则出栈栈顶，标记栈顶不在栈中。重复该操作直到栈顶元素不满足条件或者栈为空。
2. 入栈字符c，并且标记c已经在栈中。

python代码如下：

``````class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
count = collections.Counter(s)
stack = []
visited = collections.defaultdict(bool)
for c in s:
count[c] -= 1
if visited[c]:
continue
while stack and count[stack[-1]] and stack[-1] > c:
visited[stack[-1]] = False
stack.pop()
visited[c] = True
stack.append(c)
return "".join(stack)
``````

C++代码如下：

``````class Solution {
public:
string removeDuplicateLetters(string s) {
unordered_map<char, bool> visited;
unordered_map<char, int> counter;
string res = "";
for (char c : s) ++counter[c];
for (char c : s) {
--counter[c];
if (visited[c]) {
continue;
}
while (!res.empty() && counter[res.back()] && c < res.back()) {
visited[res.back()] = false;
res.pop_back();
}
res += c;
visited[c] = true;
}
return res;
}
};
``````