316_去除重复字母

类型：字符串

• 316. 去除重复字母 💛 ⭐

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

  ❓ 请去除字符串 s 中的重复字母，使每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。同：1081. 不同字符的最小子序列

  输入：s = “bcabc"输出：“abc”

  💡 贪心 + 单调栈

  一个单调递增的字符串，当然就是最小的字符串排列。当然，题目要求我们不能有重复字符，并且所有字符都得出现。因此我们在维护单调栈时需要注意以下约束：

  • 如果当前字符已经存在与栈中，则当前字符不能再入栈。
  • 在弹出栈顶字符时，如果该栈顶字符在以后都不出现了，则不能弹出，因此需要记录每个字符的剩余数量。

  class Solution:
      def removeDuplicateLetters(self, s: str) -> str:
          if not s:
              return ""
          counts = Counter(s)
          stack = []
          for c in s:
              if c in stack:
                  pass
              elif not stack or c > stack[-1] or counts[stack[-1]] <= 0:
                  stack.append(c)
              else:
                  while stack and counts[stack[-1]] > 0 and stack[-1] > c:
                      stack.pop()
                  stack.append(c)
              counts[c] -= 1
          return ''.join(stack)

  时间复杂度：O(n)