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?

By Long Luo

This article is the solution The Tricky and Clean Solution: Replace Core by 1 of Problem 856. Score of Parentheses.

There are many approaches about this problem, like Stack, Divide and Conquer, Count Cores and so on. Here shows a Tricky and Clean solution.

Intuition

The sum will be a sum of powers of \(2\), as every core (a substring \(()\), with score \(1\) ) will have it’s score multiplied by \(2\) for each exterior set of parentheses that contains that core.

Since \(s\) is a balanced parentheses string, we can replace \(()\) by \(1\), then the result is still a balanced parentheses string.

For example, \((()())\) will become \((1(1))\). The sum is \((1 + 1 \times 2) \times 2 = 1 \times 2 + 1 \times 2 \times 2 = 6\).

As a result, let \(base = 1\), we can make \(base = base \times 2\) when we meet \((\), \(base = base \div 2\) when we meet \((\), and add \(1\) when we meet \(1\).

By Long Luo

This article is the solution 4 Approaches: Stack, Array, Greedy and O(n) Time O(1) Space of Problem 946. Validate Stack Sequences.

Intuition

All elements must be pushed in in order. The key is how to pop them out?

Assuming that the value of the current top element of the stack is \(1\), and the next value to be popped in the corresponding popped sequence is also \(1\), then this value must be popped out immediately. Because the subsequent push will change the top element of the stack to a value other than \(2\), so the popped sequence of the popped numbers does not correspond.

Pushes each number in the pushed queue onto the stack, checking to see if the number is the next value to be popped in the popped sequence, and pops it if so.

Finally, check that not all the popped values are popped.

Stack

We can use a Stack to simulate the process.

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

public boolean validateStackSequences(int[] pushed, int[] popped) {
    if (popped == null || pushed.length <= 1) {
        return true;
    }

    int len = pushed.length;
    int popIdx = 0;
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < len; i++) {
        stack.push(pushed[i]);
        while (!stack.empty() && popIdx < len && stack.peek() == popped[popIdx]) {
            stack.pop();
            popIdx++;
        }
    }

    return popIdx == len;
}

Analysis

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

By Long Luo

This article is the solution Stack Solution with Easy Detailed Explanation of Problem 1249. Minimum Remove to Make Valid Parentheses.

Intuition

First we can use Brute Force to into a two-step` algorithm:

1. find all the \((\) and \()\) and get their indices;
2. determine the indices that need to be deleted;
3. creates a new string from the index of the deleted characters.

We can use a Stack to record the indices of all \((\) and \()\) s. When scanning to the end of the string, all indices remaining in the Stack are \((\) and \()\) s that do not match.

We also need to use a \(\texttt{Set}\) to keep track of unmatched \((\) and \()\) s. Then Delete each character that needs to be deleted according to the indices, and return the recreated string.

The code is as follows:

By Long Luo

This article is the solution Stack Solution with Easy Detailed Explanation of Problem 71. Simplify Path .

Intuition

We can just simulate the process from the begin to end.

First we split the given string \(\textit{path}\) into a list of strings by the slash \(/\), denoted as names. According to the canonical path in the problem description, the strings contained in names can only be the following:

1. empty string;
2. a dot .;
3. two dots ..;
4. a directory name containing only English letters, numbers, or _.

If we meet empty string or ., we can ignore them because empty string means nothing, and . means the current directory itself, so we don’t need to change directories.

If we meet .. or “directory names”, we can use a Stack to maintain each directory name in the path. When we encounter “two dots”, we need to change the directory to the parent directory. As the stack is not empty, we pop the directory of the stack. When we encounter a “directory”, we put it to the stack.

Finally we need to iterate each string in names and do the above. After all operations are completed, we connect the strings from the bottom of the stack to the top of the stack with /, and then add / at the top to indicate the root directory, and we can get the simplified Canonical path.