Implement the minRemoveValidParentheses method that removes the minimum invalid parentheses to make the text valid.
The input contains a string text that may include lowercase letters and parentheses. Your task is to remove the minimum number of parentheses so the remaining string becomes valid.
A valid parentheses string means every opening parenthesis has a matching closing parenthesis in the correct order. Normal letters should remain unchanged.
For example, lee(t(c)o)de) should become lee(t(c)o)de.
Example 1
lee(t(c)o)de)lee(t(c)o)deExample 2
a)b(c)dab(c)dExample 3
))((Use a stack to track unmatched opening parentheses and a set to mark characters that must be removed.
When a closing parenthesis appears, it is valid only if there is an unmatched opening parenthesis available. If not, mark this closing parenthesis for removal.
After scanning the string, any opening parentheses still left in the stack are also invalid. Mark them for removal, then build the final string by skipping all marked positions.
Pseudocode:
function minRemoveValidParentheses(text):
stack = empty stack of indexes
remove = empty set of indexes
for i from 0 to length of text - 1:
if text[i] == '(':
push i into stack
else if text[i] == ')':
if stack is empty:
add i to remove
else:
pop from stack
while stack is not empty:
add pop from stack to remove
result = empty string
for i from 0 to length of text - 1:
if i is not in remove:
append text[i] to result
return result