Problem Description
Explanation:
To solve this problem, we can use a stack to keep track of the indices of opening parentheses ( that are not matched with a closing parenthesis ). We will also use a set to keep track of the indices of closing parentheses ) that are not matched with an opening parenthesis (.
- Iterate through the input string
sto find and store the indices of mismatched parentheses in the stack and set. - Construct a new string by ignoring the characters at the indices stored in the stack and set.
- Return the constructed string as the minimum removed valid parentheses string.
Time Complexity: O(n) where n is the length of the input string s. Space Complexity: O(n) for the stack and set.
Solutions
class Solution {
public String minRemoveToMakeValid(String s) {
Stack<Integer> stack = new Stack<>();
Set<Integer> set = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(i);
} else if (c == ')') {
if (!stack.isEmpty()) {
stack.pop();
} else {
set.add(i);
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (!stack.isEmpty() && stack.peek() == i) {
stack.pop();
} else if (set.contains(i)) {
continue;
} else {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}Loading editor...