316. Remove Duplicate Letters

Problem Statement in English

You are given a string s which contains only lowercase letters.

You need to remove duplicate letters from s such that every letter appears once and only once in the result.

The result should be the smallest lexicographical order among all possible results.

Approach

You know that a letter can only be removed if it is not the last occurrence of that letter in the string.

Further, we only remove a letter when there is a smaller letter to its right.

This means that we can use a stack to keep track of the letters in the result.

We also need to have kept note of the highest index at which any given character occurs.

If the character at the top of the stack occurs at a higher index than at which it currently is, we know that we can remove it.

Solution in Python

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        pos = {}
        for i, char in enumerate(s):
            pos[char] = i

        stack = []

        used = set()
        for i, char in enumerate(s):
            if char in used:
                continue

            while stack and stack[-1] > char and pos[stack[-1]] > i:
                used.remove(stack.pop())

            stack.append(char)
            used.add(char)

        return "".join(stack)

Complexity

• Time: $O(n)$
  Since we iterate through $n$ elements at most.

• Space: $O(n)$
  Since we store $n$ elements in the stack at most.

And we are done.