Problem statement

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

Solution

Let us try to construct answer in greedy way: keep our answer in stack. Each time we meet new symbol:

  1. If symbol already visited, continue.
  2. While we can extract symbols from the end: it will make answer smaller and we still have this symbol later, do it, then put symbol to the stack. To quickly check if we have still symbol later, keep last_occ dictionary. See also similar problem Leetcode 1673. Find the Most Competitive Subsequence.

Complexity

It is O(n) for time and O(26) for space.

Code

class Solution:
    def smallestSubsequence(self, text):
        last_occ = {c: i for i, c in enumerate(text)}
        stack = ["!"]
        V = set()
        
        for i, symbol in enumerate(text):
            if symbol in V: continue
            
            while (symbol < stack[-1] and last_occ[stack[-1]] > i):
                V.remove(stack.pop())
           
            stack.append(symbol)
            V.add(symbol)        
        return "".join(stack)[1:]