0316._Remove_Duplicate_Letters.md

316. Remove Duplicate Letters

难度: Hard

刷题内容

原题连接

• https://leetcode.com/problems/remove-duplicate-letters/

内容描述

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 - 时间复杂度: O(N)- 空间复杂度: O(N)******

这道题让我们移除重复字母，使得每个字符只能出现一次，而且结果要按最优的字母顺序排列，前提是不能打乱其原本的相对位置。

• 先用remaining统计所有出现字母出现过的次数；
• res就是输出结果的字母顺序(list)，最后用join连接起来作为返回值(str)；
• 在cur_set(set)中的元素意味着其已经出现在最终结果中；

对s中每个字母c，首先看它在stack中有没有出现过：

1. 如果没有那么只要res最后一个字母的ASCII值大于c，且其剩余次数大于0，就将其在res和cur_set中删去，不停做此操作
2. 如果有了那么说明已经出现在最终结果中，只需要将其统计次数减去1以防后面挪动位置要做判断

做完这些后必须要把c加入到cur_set和res中去，代表c已经加入到最终结果中的目前应该处于的位置

beats 69.62%

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

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******

还有别的一些优美的解法，参考stefan的回答

递归贪心版本

class Solution:
    def removeDuplicateLetters(self, s):
        """
        :type s: str
        :rtype: str
        """
        for c in sorted(set(s)):
            suffix = s[s.find(c):]
            if set(suffix) == set(s):
                return c + self.removeDuplicateLetters(suffix.replace(c, ''))
        return ''

思路 3 - 时间复杂度: O(N)- 空间复杂度: O(N)******

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

思路 4 - 时间复杂度: O(N)- 空间复杂度: O(N)******

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