LC1249. Minimum Remove to Make Valid Parentheses

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        if s == "": return ""
 
        if all("a" <= c <= "z" for c in s):
            return s
        
        stack = []
        indexes_to_remove = set()
        last_open_index = -1
 
        for i, c in enumerate(s):
            if c == '(':
                stack.append('(')
                last_open_index = i
            elif c == ')':
                if not stack:
                    indexes_to_remove.add(i)
                else:
                    stack.pop()
        
        while stack:
            while last_open_index >= 0 and s[last_open_index] != '(':
                last_open_index -= 1
 
            indexes_to_remove.add(last_open_index)
            last_open_index -= 1
 
            stack.pop()
        
        new_s = ""
        for i, c in enumerate(s):
            if i not in indexes_to_remove:
                new_s += c
        
        return new_s

Complexity

Time: $O(n)$
Space: $O(n)$