Link to Problem and LeetCode's Solution.

Intuition

We have to find number of extra brackets that would be required.

• if (() -> at last 1 bracket would be added => +1

• if ((())A -> at we need (A) => +2 brackets

• if ((( -> we need 3 brackets i.e length of string

Approach

Iterate through the string and check the following conditions :

1. if st is empty & cur element is ) -> any how we need to add ( to it : add + 1

2. if cur is ( => always add to stack : push into stack

3. if st is not empty, and cur is ) => no bracket req, pop out )

4. else if st is not empty & i is at last index =>

   • check if cur is ) => and peek element is (, remove the peek element, if still stack size > 0 -> we'll handle those cases outside the loop, as only ( open brackets are inside stacks, that many ) closed brackets should be added. But that we'll do outside the stack.

5. else if st is not empty & i is at last idx =>

   • cur != ) => add 2 more brackets -> eg : A => add (A)

   • or ((())A => ((()))(A)

6. coming out from the loop, if stack is still not empty, add those many brackets : count += st.size()

Complexity

• Time complexity: O(N)

• Space complexity: O(M)

Code

Java

class Solution {
    public int minAddToMakeValid(String s) {
        Stack<Character> st = new Stack<>();

        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
        //if st is empty, and cur char is ) ==> add one "( "=> count++
            if (st.isEmpty() && cur == ')') count++;
            if (cur == '(') st.push(cur);
        // if not empty : remove the corresponding opening ( from stack for the curr closing ) bracket
        if (!st.isEmpty() && cur == ')') st.pop();
        //if not empty and reached the end idx & cur is ) ==> require to add closing st.len - 1 closing )
        else if (!st.isEmpty() && i == s.length() - 1 && cur == ')') {      
            // count += st.size() - 1;
            count += st.size();
            System.out.println(i + " " + st.size());
        }
        else if (!st.isEmpty() && i == s.length() - 1  && cur != ')' && cur != '(') {     //for handling cases like : ((())A => make it ((())(A) -> add 2 brackets
            count += st.size() + 2;
            System.out.println(i + " " + st.size());
        }
        }
        if (!st.isEmpty()) count += st.size();
        Iterator it = st.iterator();
         while(it.hasNext()) {
            System.out.println(it.next());          
        }
        return count;
    }
}