valid_parenthesis.py

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        #input: aart(bb)))cd((b)
        #output: aart(bb)cd(b)
        
        #1. find an open bracket. If none, empty
        #2. If I find an open bracket, increment left by 1, look for corresponding closing bracket. 
        #3. If found, reduce left by 1, start looking for next bracket. Else, plan to remove.
        #4. keep track of indices of brackets to remove.
        #5. Remove them
        
        #5.1 if you see any right sided bracket without a left first, remove it straight up.
        
        #s = "aart(bb)))cd((b)"
        s = list(s)
        left_bracket_indices = []
        
        for i in range(len(s)):
            if s[i] == "(":
                left_bracket_indices.append(i)
            
            if s[i] == ")":
                if not left_bracket_indices:
                    s[i] = ""
                else:
                    left_bracket_indices.pop()
                
        for i in left_bracket_indices:
            s[i] = ""
        
        return "".join(s)
    
    #O(n + m) m=number of left brackets without right brackets