Leetcode 1159 Solution

This article provides solution to leetcode question 1159 (smallest-subsequence-of-distinct-characters)
Categories:
Tags:
Access this page by simply typing in "lcs 1159" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/smallest-subsequence-of-distinct-characters

Solution

class Solution:
    def smallestSubsequence(self, text: str) -> str:
        m = collections.defaultdict(int)
        for i, ch in enumerate(text):
            m[ch] = i

        ans = []
        s = set()
        for i, ch in enumerate(text):
            if ch in s:
                continue

            while ans and (ans[-1][0] > ch and i <= m[ans[-1][0]]):
                s.remove(ans[-1][0])
                ans.pop(-1)

            ans.append((ch, i))
            s.add(ch)

        return "".join([ch for ch, i in ans])