## 题目描述：

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:

Given `"bcabc"`
Return `"abc"`

Given `"cbacdcbc"`
Return `"acdb"`

## 解题思路：

```枚举字符串前缀，直到遇到首个唯一字符为止，从前缀中挑选出最小的字符作为首字符。

## Python代码：

``````class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
ans = ''
for x in range(len(set(s))):
top, idx = s[0], 0
counter = collections.Counter(s)
for y in range(len(s)):
if top > s[y]:
top, idx = s[y], y
if counter[s[y]] == 1:
break
counter[s[y]] -= 1
ans += top
s = s[idx+1:].replace(top,'')
return ans
``````

### 算法的优化：

```首先计算字符串s中每一个字符出现的次数，得到字典counter

## Python代码：

``````class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
counter = collections.Counter(s)
resultSet = set()
stack = list()
for c in s:
counter[c] -= 1
if c in resultSet:
continue
while stack and stack[-1] > c and counter[stack[-1]]:
resultSet.remove(stack.pop())
stack.append(c)
return ''.join(stack)
``````

## Python代码：

``````def removeDuplicateLetters(self, s):
for c in sorted(set(s)):
suffix = s[s.index(c):]
if set(suffix) == set(s):
return c + self.removeDuplicateLetters(suffix.replace(c, ''))
return ''
``````

Pingbacks已关闭。

1. miao 发布于 2015年12月31日 13:09 #

hi, how do you know the result is 字典序最小? in 贪心算法, you have to decide whether the pick the first, second, or other ones.

2. 在线疯狂 发布于 2015年12月31日 17:41 #

这里表达的不是特别准确，应该是“最小的字符”。

3. miao 发布于 2016年1月17日 15:19 #

good implementation of the greedy algorithm, though it took me a while to understand it (I don't use python). This sentence confused me a bit "枚举字符串前缀，直到遇到首个唯一字符为止". "唯一" isn't accurate. It could be the last appearance of a non-unique character.

Nevertheless, I don't feel this could be implemented with greedy algorithm. For instance, "bcfabdefgc" -> "abdefgc", and the correct one should be "cabdefg". In fact, I feel this problem could only be solved by brute force, i.e. list all possible solutions and compare them and the get the smallest. Your thoughts?

4. miao 发布于 2016年1月18日 09:36 #

原来对字典序最小理解错了。几个实现都很好。

5. 在线疯狂 发布于 2016年1月18日 19:28 #

是的，这里的“唯一”是指当前字符在剩余字符串中不再出现。另外，测试用例"bcfabdefgc“的正确结果的确是"abdefgc"，"cabdefg"的字典序不是最小的。

6. 忍释 发布于 2017年2月20日 20:54 #

stack运用的很棒