1541. Minimum Insertions to Balance a Parentheses String

'''
Intuition

Similar to 921. Minimum Add to Make Parentheses Valid.
Just need to pay attention:
left parenthesis '(' must have a corresponding two consecutive right parenthesis '))'.

Explanation

res represents the number of left/right parentheses already added.
right represents the number of right parentheses needed.

1) case )
If we meet a right parentheses , right--.
If right < 0, we need to add a left parentheses before it.
Then we update right += 2 and res++
This part is easy and normal.

2) case (
If we meet a left parentheses,
we check if we have odd number ')' before.
If we right, we have odd ')' before,
but we want right parentheses in paires.
So add one ')' here, then update right--; res++;.
Note that this part is not necessary if two consecutive right parenthesis not required.

Because we have ), we update right += 2.
Note:Always right will
'''
#Method 1
class Solution:
    def minInsertions(self, s: str) -> int:
        right,ans=0,0
        for i in s:
            if i=='(':
                if right%2==1:
                    right-=1
                    ans+=1
                    right+=2
                else:
                    right+=2
            else:
                right=right-1
                if right<0:
                    ans+=1
                    right+=2
        return right+ ans
#Method 2
class Solution:
    def minInsertions(self, s: str) -> int:
        st=[]
        ans=0
        for i in s:
            if i=='(':
                if not st:
                    st.append(i)
                elif st[-1]=='(':
                    st.append(i)
                '''
                We will make sure that there will be surely '()' in top part of stack.
                So two pops needed
                '''
                elif st[-1]==')':
                    ans+=1
                    st.pop()
                    st.pop()
                    st.append(i)
            elif i==')':
                '''
                If stack is empty add extra '(' so that always () exists in top of stack
                '''
                if not st:
                    st.append('(')
                    ans+=1
                    st.append(i)
                elif st[-1]=='(':
                    st.append(i)
                else:
                    st.pop()
                    st.pop()
        if not st:return ans
        else:#If remaining stack is not empty
            while st:
                if st[-1]=='(':
                    ans+=2
                    st.pop()
                elif st[-1]==')':
                    ans+=1
                    st.pop()
                    st.pop()
        return ans