Minimum Insertions to Balance a Parentheses String

Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if:

In other words, we treat '(' as openning parenthesis and '))' as closing parenthesis.

For example, "())", "())(())))" and "(())())))" are balanced, ")()", "()))" and "(()))" are not balanced.

You can insert the characters '(' and ')' at any position of the string to balance it if needed.

Return the minimum number of insertions needed to make s balanced.

 

Example 1:

Input: s = "(()))"
Output: 1
Explanation: The second '(' has two matching '))', but the first '(' has only ')' matching. We need to to add one more ')' at the end of the string to be "(())))" which is balanced.

Example 2:

Input: s = "())"
Output: 0
Explanation: The string is already balanced.

Example 3:

Input: s = "))())("
Output: 3
Explanation: Add '(' to match the first '))', Add '))' to match the last '('.

Example 4:

Input: s = "(((((("
Output: 12
Explanation: Add 12 ')' to balance the string.

Example 5:

Input: s = ")))))))"
Output: 5
Explanation: Add 4 '(' at the beginning of the string and one ')' at the end. The string becomes "(((())))))))".

 

Constraints:



Solution:

class Solution {
    public int minInsertions(String s) {
        // res = number of parentheses already added
        // right = number of right parentheses needed 
        int res = 0, right = 0;
        for (int i = 0; i < s.length(); i ++) {
            if (s.charAt(i) == ')') {
                right --;
                if (right < 0) {
                    // add a left parenthese before
                    res ++;
                    right += 2;
                }
            } else {
                if (right > 0 && right % 2 == 1) {
                    // add a right parenthese before
                    res ++;
                    right --;
                }
                right += 2;
            }
        }
        return res + right;
    }
}