動機
保持原本的順序,維持字典序(小於等於) Monotonic Stack
Problem
Given a string s
, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example 1:
Input: s = "bcabc"Output: "abc"
Example 2:
Input: s = "cbacdcbc"Output: "acdb"
Constraints:
1 <= s.length <= 104
s
consists of lowercase English letters.
Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
Sol
Monotonic Stack要用但是有一個限制,只能移除多的字元,所以要移除時要看後面還有沒有其他機會
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
cnts = Counter(s) # 還有幾次可以選
stk = []
for c in s:
cnts[c] -= 1
if c not in stk:
while stk and stk[-1] >= c and cnts[stk[-1]] > 0:
stk.pop()
stk += c,
return ''.join(stk)