316 Remove Duplicate Letters

题目

Remove Duplicate Letters

题解

题目要求返回最小字典序的子字符串，并且每个字母都必须要出现且仅出现一次。

首先，我们从最小字典序着手，只要子字符串满足严格单调递增，我们就能确定它是最小字典序的。而严格单调递增的性质可以用栈来维护：我们逐个取出字符c，将其与栈顶字符做比较，若栈顶字符大于c，则进行弹栈操作，直到栈顶不再含有大于c的字符，然后把c压入栈顶。

接着，我们来分析下每个字母仅出现一次这个约束条件，当我们把字母l加入子字符串 \(s_0s_1 \dots s_n\) 后，再次遇到了字母l，这时该怎么办呢？这时我们直接忽略后面的字母l即可，因为在严格单调递增的字符串 \(s_0 \dots l \dots s_n\) 中，用后一个l取代前一个l，相当于把l向后移，而这对减少字典序没有帮助，因为l后面的字符必然比l大。

最后，由于每个字母都必须要出现一次，我们可能无法构造严格单调递增的子字符串，那么该怎么办呢？假设我们在构造完严格单调递增的子字符串之后，发现少了一个字母l，而字母l的每个候选位置都会破坏严格单调递增的性质，那么我们应该选最靠后的字母l，因为它能最大程度地减少对字符串字典序的增加。

经过上面的分析，我们就能够得出大致的算法了，直接看下面的代码吧。

代码

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        letter_last_index = {}
        for index, letter in enumerate(s):
            letter_last_index[letter] = index

        border = chr(0)
        stack = [border]
        occurred = set()
        for index, letter in enumerate(s):
            if letter in occurred:
                continue

            top = stack[-1]
            while letter < top and index < letter_last_index[top]:
                stack.pop()
                occurred.discard(top)
                top = stack[-1]

            stack.append(letter)
            occurred.add(letter)

        stack.remove(border)
        return ''.join(stack)