# 316 Remove Duplicate Letters

### 316. Remove Duplicate Letters

Hard

class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
remaining = collections.defaultdict(int)
for c in s:
remaining[c] += 1
res, stack = [], set()
for c in s:
if c not in stack:
while res and res[-1] > c and remaining[res[-1]] > 0:
stack.remove(res.pop())
res.append(c)
remaining[c] -= 1
return ''.join(res)


递归贪心版本
class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
for c in sorted(set(s)):
suffix = s[s.index(c):]
if set(suffix) == set(s):
return c + self.removeDuplicateLetters(suffix.replace(c, ''))
return ''

class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
result = ''
while s:
i = min(map(s.rindex, set(s)))
c = min(s[:i+1])
result += c
s = s[s.index(c):].replace(c, '')
return result

class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
rindex = {c: i for i, c in enumerate(s)}
result = ''
for i, c in enumerate(s):
if c not in result:
while c < result[-1:] and i < rindex[result[-1]]:
result = result[:-1]
result += c
return result


apachecn/AiLearning