Problem Statement

Given a string s, remove duplicate letters so that every letter that appears in s appears exactly once in the result. You may only delete characters. The letters that survive keep the order they had in s.

Among all the results you can reach that way, return the one that is smallest in lexicographical order.

A string is in the smallest lexicographical order if it appears first in a dictionary. For example, "abc" is smaller than "acb" because "abc" comes first alphabetically.

Note that this does not mean sorting the letters. "zabccde" gives "zabcde" and not "abcdez", because the z comes first in the input and deleting characters can never move it.

Examples:

1. • Input: "babac"
   • Expected Output: "abc"
   • Justification:
     • After removing 1 b and 1 a from the input string, we can get bac, and abc strings. The final answer is 'abc', which is the smallest lexicographical string without duplicate letters.
2. • Input: "zabccde"
   • Expected Output: "zabcde"
   • Justification: Removing one of the 'c's forms 'zabcde', the smallest string in lexicographical order without duplicates.
3. • Input: "mnopmn"
   • Expected Output: "mnop"
   • Justification: Removing the second 'm' and 'n' gives 'mnop', which is the smallest possible string without duplicate characters.

Constraints:

• 1 <= s.length <= 10⁴
• s consists of lowercase English letters.

Try it yourself

Try solving this question here: