Minimum Add to Make Parentheses Valid

 A parentheses string is valid if and only if:

It is the empty string,

It can be written as AB (A concatenated with B), where A and B are valid strings, or

It can be written as (A), where A is a valid string.

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.

For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))".

Return the minimum number of moves required to make s valid.

 

Example 1:

Input: s = "())"

Output: 1

Example 2:

Input: s = "((("

Output: 3

 Logic in Words:

1. If the character is '(', push it.

2. If the character is ')', then:

   • If the stack is empty, that means there's no '(' to match → count++ (you need to insert an '(').

   • If the top is '(', pop it (they match).

   • Otherwise (top is also ')'), it’s unmatched → count++.

class Solution {

    public int minAddToMakeValid(String s) {

       

         Stack<Character> st = new Stack<>();

        int count = 0;

        for (char ch : s.toCharArray()) {

            if (ch == '(') {

                st.push(ch);

            } else { // ch == ')'

                if (st.isEmpty()) {

                    count++; // no '(' to match

                } else {

                    st.pop(); // match found, remove one '('

                }

            }

        }

        // stack.size() gives unmatched '('

        return count + st.size();

    }

}