Given a string s, return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.
Example 1:
Input: s = "bcabc"
Output: "abc"
Example 2:
Input: s = "cbacdcbc"
Output: "acdb"
Constraints:
-
1 <= s.length <= 1000 -
sconsists of lowercase English letters.
Note: This question is the same as 316: https://leetcode.com/problems/remove-duplicate-letters/SOLUTION:
class Solution:
def smallestSubsequence(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)
# class Solution:
# def smallestSubsequence(self, s: str) -> str:
# n = len(s)
# numdist = len(set(s))
# smallest = ""
# paths = [(s[i], [i]) for i in range(n)]
# while len(paths) > 0:
# curr, indexes = paths.pop()
# if smallest:
# if curr < smallest and len(curr) == numdist:
# smallest = curr
# for j in range(indexes[-1] + 1, n):
# if s[j] not in curr:
# paths.append((curr + s[j], indexes + [j]))
# elif len(curr) == numdist:
# smallest = curr
# return smallest
Top comments (0)