By Long Luo

This article is the solution Greedy Solution with Easy Detailed Explanation of Problem 763. Partition Labels.

Greedy

If we want to partition, we must maintain Two Pointers at the beginning and the end of a section. The Next Partition will start at the end of last Partition.

While scanning the string, if all the characters in the Partition only appear in the Partition, we can Partition it.

As the picture below shows, the farthest position of all the chars is no more than \(8\), so we can partition it.

and so on.

By Long Luo

This article is the solution HashMap Solution with Detailed Explanation of Problem 895. Maximum Frequency Stack.

Intuition

Let’s look at the problem description first.

1. \(\texttt{FreqStack()}\) constructs an empty frequency stack.
2. void \(\texttt{push(int val)}\) pushes an integer val onto the top of the stack.
3. int \(\texttt{pop()}\) removes and returns the most frequent element in the stack.
4. If there is a tie for the most frequent element, the element closest to the stack’s top is removed and returned.

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

1. Pop the stack by the max frequency;
2. Among all the elements with the same (maximum) frequency, pop the element closest to the stack’s top.

To simplify the problem, let’s just ignore rule 2 for now, it looks easier.

Step 1

We care more about the frequency of the elements. We can use \(\texttt{HashMap}\) to record the frequency of each element.

Additionally, we also care about max Frequency, the current maximum frequency of any element in the stack. we use the \(\textit{maxFreq}\) to store the maximum frequency.

The code is as follows.

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)\)