By Long Luo

First, let’s look at the problem description:

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

The requirements of the problems can be listed in 3 rules:

1. remove duplicate letters;
2. the order of characters in the deduplicated string cannot disrupt the relative order of the characters in s;
3. among all deduplicated strings that meet the previous requirement, the one with the smallest lexicographical order is the final result.

# Step 1

Let’s just ignore rule 3 for now, and use stack to follow rule 1 and rule 2:

Use the boolean array inStack to record the chars in the stack to deduplication, so the chars in the stack are not duplicated.

If you enter s = “bcabc”, the result is “bca”, which already meets rule 1 and 2. However, the right answer is “abc”.

So if we want to meet the rule 3 and follow the lexicographic order, what should we do?

# Step 2

While inserting the character ‘a’ into the stack, we needs to know, which is greater in the lexicographical order of the character ‘a’ and the previous two characters ‘b’ and ‘c’?

If the current char ‘a’ is lexicographically smaller than the previous character, it may be necessary to pop the previous character from the stack to put ‘a’ first.

If s = “bcac”, the result is “ac”, but the right answer should be “bac”.

Since there is only one ‘b’ in s, the character ‘b’ should not be popped even if its lexicographical order is smaller than the character ‘b’.

How to fix it?

# Step 3

We will only pop the element when stack.peek() > ch. At this time, we can divide it to.

1. If the char stack.peek() will appear later, pop it out;
2. If the stk.peek() char will not appear afterward, and it was said earlier that there will be no duplicate elements in the stack, then you cannot pop it out, otherwise you will lose this character forever.

The key is to count the freqency of diffent chars in the string and we get the final answer.

## Analysis

• Time Complexity: $O(N)$
• Space Complexity: $O(N)$

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗