Stack Topological Sort Simulation
Intermediate Level

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
Input:
text (string) = lee(t(c)o)de)
Return:
(string) lee(t(c)o)de
Example 2
Input:
text (string) = a)b(c)d
Return:
(string) ab(c)d
Example 3
Input:
text (string) = ))((
Return:
(string)

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
Run your code to see the result.