LeetCode //C - 316. Remove Duplicate Letters

题目：给定一个字符串，删除字符串中重复字母，使得每个字母只出现一次。需要保证结果字符串中的字母顺序和原来一致，不改变原来的字母间的相对位置。

解法：

这是一个栈的问题。我们可以使用一个栈来保存我们想要保留的字符，然后遍历整个字符串。当我们遇到一个新的字符时，我们需要确定它是否已经在栈中。如果在，我们就跳过它。如果不在，我们就需要考虑它是否可以放入栈中。当我们遇到一个已存在于栈顶的字符时，我们就需要将栈顶字符移除，直到我们找到一个可以放入的字符或者栈为空。

以下是一个Python的解法：

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        stack = []
        letters = [0] * 26
        for char in s:
            letters[ord(char) - ord('a')] += 1
        
        for char in s:
            if char not in stack:
                while stack and char < stack[-1] and letters[ord(stack[-1]) - ord('a')] > 0:
                    stack.pop()
                stack.append(char)
                letters[ord(char) - ord('a')] -= 1
        
        return ''.join(stack)

这个解法的时间复杂度为O(N)，空间复杂度为O(N)。

这个解法的核心在于，我们维护了一个字符计数数组，以及一个字符栈。我们遍历字符串中的每一个字符，如果这个字符没有在栈中，我们就将它放入栈中。如果这个字符在栈中已存在，我们就跳过它。当我们遇到一个小于栈顶元素的字符时，我们就需要将栈顶元素移除，直到我们找到一个可以放入的字符或者栈为空。

这个解法保证了字符的相对位置不变，并且只包含每个字符一次。