LC 1249 [M] Minimum Remove to Make Valid Parentheses - ALawliet/algorithms GitHub Wiki

intuitive? Y

(NOT a recursion/backtracking/DP problem but the classic stack problem!)

• invalid open indexes stack, invalid close indexes stack
• push opens
• on close, pop open if there is one, else push close
• combine the lone opens and closes indexes, and return the string without them

T: O(n)
S: O(n)

there is a S: O(1) solution if you just count but it's probably not needed

---

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        l, r = [], []
        
        for i, x in enumerate(s):
            if x == '(':
                l.append(i)
            elif x == ')':
                if l:
                    l.pop()     # valid, close a pair
                else:
                    r.append(i) # invalid
        
        # unpaired = set(l + r) # you don't really need a set but it speeds up time, list is ok 
        unpaired = l + r

        return [x for i, x in enumerate(s) if i not in unpaired]

class Solution:
    def minRemoveToMakeValid(self, s) :
        stack=[]
        split_str=list(s)
        for i in range(len(s)):
            if s[i]=='(':
                # if current char is '(' then push it to stack
                stack.append(i)
            elif s[i]==')':
                # if current char is ')' then pop top of the stack
                if len(stack) !=0:
                    stack.pop()
                else:
                    # if our stack is empty then we can't pop so make  current char as ''
                    split_str[i]=""
        for i in stack: # the invalid parens
            split_str[i]=""
        return '' .join(split_str)