LC-1081 Medium LeetCode

1081. Smallest Subsequence of Distinct Characters

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 62% Topics: String, Stack, Greedy, Monotonic Stack

Reading material

Strings 12 min Stacks & Queues 11 min Greedy 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

import collections


class Solution(object):
    def smallestSubsequence(self, text):
        """
        :type text: str
        :rtype: str
        """
        count = collections.Counter(text)

        lookup, stk = set(), []
        for c in text:
            if c not in lookup:
                while stk and stk[-1] > c and count[stk[-1]]:
                    lookup.remove(stk.pop())
                stk += c
                lookup.add(c)
            count[c] -= 1
        return "".join(stk)

Solution from kamyu104/LeetCode-Solutions · MIT