Minimum Insertions to Balance a Parentheses String

Problem

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

• Any left parenthesis '(' must have a corresponding two consecutive right parenthesis '))'.
• Left parenthesis '(' must go before the corresponding two consecutive right parenthesis '))'.

In other words, we treat '(' as an opening parenthesis and '))' as a 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.

Examples

Example 1:

Input: s = "(()))"
Output: 1
Explanation: The second '(' has two matching '))', but the first '(' has only ')' matching. We need 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 '('.

Constraints:

• 1 <= s.length <= 105
• s consists of '(' and ')' only.

Solution

Method 1 – Greedy Counting

Intuition

We need to match every '(' with two consecutive ')'. By scanning the string from left to right, we can keep track of how many ')' are needed and how many insertions are required. If we see a '(', we expect two ')' to follow. If we see a ')', we check if it completes a pair or if we need to insert more ')' or '('.

Approach

1. Initialize need (number of ')' needed) and insertions (number of insertions required) to 0.
2. Iterate through each character in s:
   • If '(', increment need by 2. If need is odd, insert one ')' and decrement need by 1.
   • If ')', decrement need by 1. If need becomes negative, insert one '(', reset need to 1.
3. After processing, add any remaining need to insertions.
4. Return insertions.

Complexity

• ⏰ Time complexity: O(n), where n is the length of s, since we scan the string once.
• 🧺 Space complexity: O(1), only constant extra space is used.

Code

Python

class Solution:
    def minInsertions(self, s: str) -> int:
        need = 0
        insertions = 0
        for c in s:
            if c == '(': 
                need += 2
                if need % 2:
                    insertions += 1
                    need -= 1
            else:
                need -= 1
                if need < 0:
                    insertions += 1
                    need = 1
        return insertions + need

Java

class Solution {
    public int minInsertions(String s) {
        int need = 0, insertions = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                need += 2;
                if (need % 2 == 1) {
                    insertions++;
                    need--;
                }
            } else {
                need--;
                if (need < 0) {
                    insertions++;
                    need = 1;
                }
            }
        }
        return insertions + need;
    }
}

C++

class Solution {
public:
    int minInsertions(string s) {
        int need = 0, insertions = 0;
        for (char c : s) {
            if (c == '(') {
                need += 2;
                if (need % 2 == 1) {
                    insertions++;
                    need--;
                }
            } else {
                need--;
                if (need < 0) {
                    insertions++;
                    need = 1;
                }
            }
        }
        return insertions + need;
    }
};