1541. Minimum Insertions to Balance a Parentheses String

class Solution:
    def minInsertions(self, s: str) -> int:
        """ tc O(N)  sc O(N)
        main idea: 1. each time encountered (, push into st; each time encountered ), chech st[-1]  is empty, (  or )   
                                                                                        if empty,  need to insert (
                                                                                        if ( means we have first ), push into st 
                                                                                        if ), pop()  twice 
                  
                   2. decluter st, if st[-1] is (, pop() and cnt +2 
                                    if st[-1] is ) cnt -= 1 
        """
        st, cnt = [],0
        for c in s:
            if c == '(':
                if st and st[-1]==')':
                    # st.append(')')
                    # st.pop()
                    st.pop()
                    st.pop()
                    cnt += 1 
                st.append(c)
            else:
                if not st:
                    st.append('(') #here we guaranteen in stack there is only () there is not )( ==> when st[-1], len(st) is at least 2 
                    cnt += 1 
                    st.append(c)
                elif st and st[-1] == '(':
                    st.append(c)
                elif st and st[-1] == ')':
                    st.pop()
                    st.pop()
        while st:
            if st[-1] == '(':
                st.pop()
                cnt += 2
            else:
                if len(st) > 1:
                    st.pop()
                    st.pop()
                    cnt += 1
                else:
                    st.pop()
                    cnt += 2
        return cnt 

class Solution:
    def minInsertions(self, s: str) -> int:
        """ tc O(N)  sc O(1)
        main idea: keep track of #  close paratheses ) and # of parathesis is inserted;     answer = ins + closes 
                    two cases (1) c == (
                                
                                
                              (2) c == )
        """
        ins = closes = 0
        for c in s:
            if c == '(':
                if closes % 2 : # imply there is an extra )
                    ins += 1
                    closes -= 1 #means after new ( is inserted, there extra ) is consumed 
                closes += 2
            else: # c == )
                closes -= 1
                if closes < 0 : # there is extra ) so far,  we need to insert ( to pair it 
                    ins += 1
                    closes += 2 
        return closes + ins