710072. Remove Invalid Parentheses
Remove Invalid Parentheses
Slug: remove-invalid-parentheses
Difficulty: Hard
Id: 710072
Summary
Given a string containing only parentheses, remove all the invalid parentheses from the string. A parenthesis is considered valid if it's correctly nested and balanced. For example, ((())) is a valid sequence of parentheses while (())) is not because the closing parenthesis does not match the opening one.
Detailed Explanation
To solve this problem, we can use a stack-based approach to keep track of the opening and closing parentheses. We iterate through the string from left to right, and whenever we encounter an opening parenthesis, we push it onto the stack. When we encounter a closing parenthesis, we check if the stack is empty or the top of the stack does not match the current closing parenthesis. If either condition is true, we remove the invalid closing parenthesis.
Here's a step-by-step breakdown of the solution:
- Initialize an empty string
resultto store the valid parentheses. - Iterate through the input string from left to right.
- For each character in the input string:
- If the character is an opening parenthesis, push it onto the stack and append it to the result string.
- If the character is a closing parenthesis:
- Check if the stack is empty. If so, remove the current closing parenthesis because it does not have a matching opening parenthesis.
- Otherwise, check if the top of the stack matches the current closing parenthesis. If not, remove the current closing parenthesis because it's invalid.
- Return the result string containing only the valid parentheses.
The time complexity of this solution is O(n), where n is the length of the input string, because we iterate through the string once. The space complexity is also O(n) due to the stack used to keep track of the opening and closing parentheses.
Optimized Solutions
Java
public String removeInvalidParentheses(String s) {
StringBuilder result = new StringBuilder();
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(c);
result.append(c);
} else if (c == ')') {
if (!stack.isEmpty() && stack.peek() == '(') {
stack.pop();
result.append(c);
} else {
result.deleteCharAt(result.length() - 1);
}
}
}
while (!stack.isEmpty()) {
result.append(stack.pop());
}
return result.toString();
}