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:

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
34
35

public String minRemoveToMakeValid(String s) {
    if (s == null || s.length() <= 0) {
        return s;
    }

    int len = s.length();
    StringBuilder sb = new StringBuilder(len);
    Stack<Integer> stack = new Stack<>();
    Set<Integer> idx = new HashSet<>();
    for (int i = 0; i < len; i++) {
        char ch = s.charAt(i);
        if (ch == '(') {
            stack.push(i);
            idx.add(i);
        } else if (ch == ')') {
            if (!stack.empty()) {
                idx.remove(stack.pop());
            } else {
                idx.add(i);
            }
        }
    }

    while (!stack.empty()) {
        idx.add(stack.pop());
    }

    for (int i = 0; i < len; i++) {
        if (!idx.contains(i)) {
            sb.append(s.charAt(i));
        }
    }

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