1249. Minimum Remove to Make Valid Parentheses

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        """ tc O(N) sc O(N)
        main idea: to make valid + since we can only remove =>  need to count to keep current substring balanced => 
                how to minimize remove steps  =>greedy ? XXX  use stack to track open parathesis 
                1. push index into stack when we see a (
                2. pop off stack previous index of ( when we see a ), otherwise set char of s at current index  as ''
                                                                                because this ) need to be removed 
                3. clear out stack, set char of s at  indexes in the stack that has only (  
                
        """
        s = list(s)
        st = []
        for i,c in enumerate(s):
            if c =='(':
                st.append(i)
            elif c == ')':
                if st:
                    st.pop()
                else:
                    s[i] = ''
        while st:
            s[st.pop()] = ''
        return ''.join(s)

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        """ tc O(N) sc O(1) actually if res is considered extra space, will be sc O(N)
        main idea: two round with counter for open and close parenthesis
            1. one loop get all the closed parenthesis 
            2. second loop, check if current char is (,  ), or other alpha   
                                                (1) if c == (,  check if there are future ) to pair: yes, append ( to res, otherwise skip c  
                                                (2) if c ==  ), check if there are ( so far:  if no, skip, otherwise, ) cnt -1 appenc c into res 
                                                (3) if c is alpha, append into res 
        """
        res = []
        opens = closes = 0
        for c in s:
            if c == ')':
                closes += 1 # cnt number of ) in the future at index 0 
                
        for c in s:
            if c == '(':
                opens += 1
                if closes > 0:
                    closes -= 1 # can make a pair, future available ) decrease by 1 
                    res.append(c)
            elif c == ')':
                    # so far # of )in the future  waiting to be paired 
                if opens > 0 :
                    opens -= 1 # cancel out previous paired (
                    res.append(c)
                else:
                    closes -= 1 # remove invalid )  
            else:
                res.append(c)
        return ''.join(res)
        

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        """ tc O(N) sc O(1)
        main idea: 
                1. from back to front,remove extra (, get the right ptr of non-empty char 
                2. start with right pointer, from front to back, remove extra )
                3. return first non-empty substring 
        """
        s = list(s)
        n  =  r = len(s)
        balance = 0 
        for j in range(n-1,-1,-1):
            if s[j] == ')':
                balance += 1
            elif s[j] == '(':
                if balance == 0:
                    continue
                balance -= 1
            r -= 1
            s[r] = s[j]
        l = balance2 = 0
        for i in range(r,n):
            if s[i] == '(':
                balance2 += 1
            elif s[i] == ')':
                if balance2 == 0:
                    continue
                balance2 -= 1
            s[l] = s[i]
            l += 1
        return ''.join(s[:l])