• If the stack is empty, then this means that you will need to remove this right parenthesis from the input string. So you add its index in a set to remove at the end.
• If the stack is not empty, then you pop out an element from the stack.

At the end, you will come across two scenarios: - The stack is empty, in which case you are good to go by removing only the early right parentheses indexes you have already saved. - Or, the stack is non-empty, which means that there are a bunch of additional left parentheses unmatched. In that case, you remove the indexes remaining in the stack as well.

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        stack = []
        indexes_to_remove = set()
        for i,l in enumerate(s):
            if l in "()":
                if not stack and l == ")":
                    indexes_to_remove.add(i)
                elif l == "(":
                    stack.append(i)
                else:
                    stack.pop()

        # add the remaining of the stack
        indexes_to_remove = indexes_to_remove.union(set(stack))
        return "".join([l for i,l in enumerate(s) if i not in indexes_to_remove])

If we wanted to run it on an example:

Solution().minRemoveToMakeValid('m(a(d)))')

## 'm(a(d))'

The time complexity of this solution is \(O(N)\), since there is no nested for loop. Note that despite the fact that go over N twice, this is still \(O(N)\) as \(O(cN)\), where \(c\) is a constant and not an inpiut maps to \(O(N)\). The space complexity is again O(N): up to \(N\) elements in the stack, up to \(N\) elements in the set, hence the result is \(O(N)\).