[Leetcode][1249. Minimum Remove to Make Valid Parentheses] Stack Solution with Easy Detailed Explanation

By Long Luo

This article is the solution of Problem 1249. Minimum Remove to Make Valid Parentheses.

Stack

Explanation

First we can use brute force ideas 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 use a stack to store 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 collection to keep track of unmatched ( and ) s. Then Delete each character that needs to be deleted according to the indices, returning the recreated string.

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