# [Leetcode][316. Remove Duplicate Letters] The Detailed Explanation with 3-Steps to Understand the Stack Approach

**By Long Luo**

This article is the solution of Problem 316. Remove Duplicate Letters.

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 inlexicographicalorder among all possible results.

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

- remove duplicate letters;
- the order of characters in the deduplicated string cannot disrupt the relative order of the characters in s;
- 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:

1 | public static String removeDuplicateLetters_stk_1(String s) { |

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.

1 | public static String removeDuplicateLetters_stk_2(String s) { |

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.

- If the char
`stack.peek()`

will appear later, pop it out; - 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.

1 | public static String removeDuplicateLetters(String s) { |

## 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. 😉😃💗