By Long Luo

This article is the solution The Detailed Explanation with 3-Steps to Understand the Stack Approach of Problem 316. Remove Duplicate Letters.

Intuition

First, let’s look at the problem description:

Given a string \(\textit{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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public static String removeDuplicateLetters_stk_1(String s) {
    Stack<Character> stack = new Stack<>();
    boolean[] inStack = new boolean[26];
    int len = s.length();
    for (int i = 0; i < len; i++) {
        char ch = s.charAt(i);
        if (inStack[ch - 'a']) {
            continue;
        }

        stack.push(ch);
        inStack[ch - 'a'] = true;
    }

    StringBuilder sb = new StringBuilder(stack.size());
    while (!stack.empty()) {
        sb.append(stack.pop());
    }

    return sb.reverse().toString();
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public static String removeDuplicateLetters_stk_2(String s) {
    Stack<Character> stack = new Stack<>();
    boolean[] inStack = new boolean[26];
    int len = s.length();
    for (int i = 0; i < len; i++) {
        char ch = s.charAt(i);
        if (inStack[ch - 'a']) {
            continue;
        }
        while (!stack.empty() && stack.peek() > ch) {
            inStack[stack.pop() - 'a'] = false;
        }

        stack.push(ch);
        inStack[ch - 'a'] = true;
    }

    StringBuilder sb = new StringBuilder(stack.size());
    while (!stack.empty()) {
        sb.append(stack.pop());
    }

    return sb.reverse().toString();
}

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 \(\texttt{stack.peek()} \gt ch\). At this time, we can divide it to.

1. If the char \(\texttt{stack.peek()}\) will appear later, pop it out;
2. If the \(\texttt{stack.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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public static String removeDuplicateLetters(String s) {
    Stack<Character> stack = new Stack<>();
    int[] cnt = new int[26];
    boolean[] inStack = new boolean[26];
    int len = s.length();
    for (int i = 0; i < len; i++) {
        cnt[s.charAt(i) - 'a']++;
    }
    for (int i = 0; i < len; i++) {
        char ch = s.charAt(i);
        cnt[ch - 'a']--;
        if (inStack[ch - 'a']) {
            continue;
        }
        while (!stack.empty() && stack.peek() > ch) {
            if (cnt[stack.peek() - 'a'] <= 0) {
                break;
            }

            inStack[stack.pop() - 'a'] = false;
        }

        stack.push(ch);
        inStack[ch - 'a'] = true;
    }

    StringBuilder sb = new StringBuilder(stack.size());
    while (!stack.empty()) {
        sb.append(stack.pop());
    }

    return sb.reverse().toString();
}

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