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/
SOLUTION:
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
lastIndex = {}
for i, c in enumerate(s):
lastIndex[c] = i
used = set()
stack = []
for i, c in enumerate(s):
if c in used:
continue
while len(stack) > 0 and s[stack[-1]] > c and i < lastIndex[s[stack[-1]]]:
curr = stack.pop()
if s[curr] in used:
used.remove(s[curr])
stack.append(i)
used.add(c)
return "".join(s[i] for i in stack)
Top comments (0)