DEV Community

Abhishek Chaudhary

Posted on

Smallest Subsequence of Distinct Characters

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`
• `s` consists 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)
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
``````