1081. Smallest Subsequence Of Distinct Characters

Problem Statement in English

You’re given a string s, which consists of lowercase English letters. You need to return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.

Approach

Fundamentally, when we’re encountering a character that’s smaller than the existing characters in our temporary answer, we can get rid of that offending character in favor of the new one if we know that the offending character will appear again later in the string. This is because we want to ensure that all distinct characters are included in the final answer.

So we’re going to need to store the latest index of each character in the string so that we can check if a character will appear again later in the string.

Along with this, we will build our temporary answer using a stack.

When we encounter a character, we will check if it is smaller than the last character in our stack and if the last character in our stack will appear again later in the string. If both conditions are true, we can pop the last character from our stack and add the new character to our stack.

And we will also need to keep track of which characters have already been added to our stack so that we don’t add duplicates.

At the end we need to return the characters in our stack as a string.

And we’re done!

Solution in Python

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        latest = {}

        for i, c in enumerate(s):
            latest[c] = i

        stack = []
        added = set()

        for i, c in enumerate(s):
            if c in added: continue
            while stack and c < stack[-1] and latest[stack[-1]] > i:
                added.remove(stack.pop())

            stack.append(c)
            added.add(c)

        return "".join(stack)

Complexity

• Time: $O(n)$
  Since we are iterating through the string once and performing constant time operations for each character, the time complexity is linear with respect to the length of the string.

• Space: $O(1)$
  Since we are using a fixed-size array to store the latest index of each character and a stack to build our answer, the space complexity is constant with respect to the number of distinct characters in the string (which is at most 26 for lowercase English letters).

And we are done.